21. 将两个有序列表融合
Linked List 数据结构也在面试中经常出现,作为很好处理客户信息存储的结构很方便,也是重点必会项目之一,看看我们如何教懂白月光,成功邀约看电影吧。
小白渣翻译
你将获得两个排序链表 list1 和 list2 的头。
将两个列表合并为一个排序列表。该列表应该通过将前两个列表的节点拼接在一起来形成。
返回合并链表的头。
例子
这里是小白理解
这种题目我们首先把他进行下条件梳理
- 链表类题目,我们首先要对链表结构有一定了。
- 题目描述意思说的简单一些,就是将两个有序链表的元素,最终都放在一个ListNode中,但是这里描述有些问题,他没有提到有序,如果加上,对于大家理解会更加清晰一些。
但是这题有些不清晰就在于得需要每个结果适合另外一个ListNode中的值有关系,而且相比于Array或者String要对ListNode List熟悉一些。,这时候黑长直女神过来问:小白,你这题怎么思考的啊?
小白内心镇定:小美,《年会不能停》有机会一起去看看吧?
哦,不是,这道题咱们可以考虑下用个dummy Node(虚拟节点)来辅助做题
-
首先,我们为新的合并链表创建一个虚拟节点
-
接下来我们创建两个指针,一个指向list1,另一个指向list2。
-
现在遍历列表,直到其中一个列表耗尽为止。
-
如果指向任一列表的节点的值小于另一个指针,则将该节点添加到我们的合并列表中并递增该指针。
小美:小伙子,可以啊,这不仅逻辑感人,阅读理解也有俩下子!不过电影票要你买单哦。
小白:没问题,谁叫为了“真爱”呢
真正面试环节
面试官:你可以解答这道”融合链表“的题目吗,来看看你对linked List结构的理解。
小白:嘿嘿,这不巧了么这不是
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 首先,确保链表都不为空
if (list1 != null && list2 != null) {
// 如果链表1的第一个值小于链表2的第一个值
if(list1.val < list2.val) {
// 回归算法,找到链表1的next值
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
// 如果链表1的值大于链表2遍历的值
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
// 如果链表1为空,那么直接返回链表2
if(list1 == null) {
return list2;
}
return list1;
}
小明:OK,完事儿,等着面试官来表扬自己吧。他肯定会说:小子,你是个好手!工位都给你准备好了,工资你说了算。
面试官:矮油,不错啊,不过你这能不能写个测试啊。
小明OS:今年这个找工市场,人言洛阳花似锦,偏我来时不逢春。。。不是,怎么还让我些test case 啊!
static void printList(ListNode node) {
while (node != null) {
System.out.print(node.val + " ");
node = node.next;
}
}
public static void main(String[] args) {
ListNode list1 = new ListNode(1);
ListNode list2 = new ListNode(1);
list1.next = new ListNode(2);
list1.next.next = new ListNode(4);
list2.next = new ListNode(3);
list2.next.next = new ListNode(4);
ListNode mergeTwoLists = mergeTwoLists(list1, list2);
printList(mergeTwoLists);
}
小白:您好,面试官,这回可以了吧,我终于有钱请小美看电影了!
============================================================================
🍀🍀🍀🍀🍀🍀更多算法题解请看 面试数据结构与算法总结分类+leetcode目录【基础版】
编码道路漫漫,只要先看脚下的路,徐徐前进即可。
原文地址:https://blog.csdn.net/u014739136/article/details/136024959
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_66653.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!