LeetCode高频题21. 合并两个有序链表

链表"/>

LeetCode高频题21. 合并两个有序链表

LeetCode高频题21. 合并两个有序链表

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

文章目录

• LeetCode高频题21. 合并两个有序链表
• • @[TOC](文章目录)
• 题目
• 一、审题
• 笔试AC：链表转数组，再转链表
• 可以再尝试一下优化空间，别用堆，用少数俩变量，外部排序，谁小先挂谁
• 后来我看了官方解题思想，人家那思路更简单
• 总结

题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

一、审题

示例：1

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

笔试AC：链表转数组，再转链表

最蠢的办法就是拿个小根堆转移一下，或者数组转移排序，
然后挨个弹出重新组织为链表，空间复杂度高，适合笔试AC

问题不大：

public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {//直接用小根堆，PriorityQueue<ListNode> heap = new PriorityQueue<>(new myComparator());while (l1 != null) {heap.add(l1);ListNode p1 = l1;l1 = l1.next;p1.next = null;}while (l2 != null) {heap.add(l2);ListNode p2 = l2;l2 = l2.next;p2.next = null;}ListNode head = heap.poll();ListNode cur = head;while (!heap.isEmpty()){cur.next = heap.poll();cur = cur.next;}return head;}public static class myComparator implements Comparator<ListNode>{@Overridepublic int compare(ListNode o1, ListNode o2){return o1.val - o2.val;}}

测试一把：

public static void test(){ListNode l1 = new ListNode(1);ListNode l12 = new ListNode(2);ListNode l13 = new ListNode(3);l1.next = l12;l12.next = l13;ListNode l2 = new ListNode(1);ListNode l22 = new ListNode(3);ListNode l23 = new ListNode(4);l2.next = l22;l22.next = l23;Solution solution = new Solution();ListNode res = solution.mergeTwoLists2(l1, l2);while (res != null){System.out.print(res.val + " ");res = res.next;}}public static void main(String[] args) {test();}

测试一把：

1 1 2 3 3 4 
Process finished with exit code 0

看看LeetCode啥反应


就这方法已经很牛逼了

可以再尝试一下优化空间，别用堆，用少数俩变量，外部排序，谁小先挂谁

与归并排序算法中的merge过程一模一样
只不过这里是链表

【1】10大排序算法之四：归并排序【稳定的】，复杂度中，系统常用归并排序

（-1）4个变量
p1指向head1，next1=p1.next
p2指向head2，next2=p2.next

（0）对比p1和p2的值
（1）遇到p1<=p2，让p1.next=p2，然后n1和p1同步走，回到（0）
（2）遇到p1>p2，让p2.next=p1，然后n2和p2同步走，回到（0）
（3）直到n1或者n2为空，把剩下的转移完

比如，上图
（0）对比p1和p2的值
（1）遇到p1<=p2，让p1.next=p2，然后n1和p1同步走，看绿色那，回到（0）
得到的结果像这样

（2）遇到p1>p2，让p2.next=p1，然后n2和p2同步走，看橘色之后，粉色那，回到（0）
得到这样的结果

（1）遇到p1<=p2，让p1.next=p2，然后n1和p1同步走，看蓝色那，回到（0）
得到的结果像这样

（2）遇到p1>p2，让p2.next=p1，然后n2和p2同步走，看红色那，回到（0）
得到这样的结果

（3）直到n1或者n2为空，把剩下的转移完

手撕代码：
这个代码我可能设计有问题，思路是OK，但是细节没有扣出来，先放放，我的失误，后面补上。

后来我看了官方解题思想，人家那思路更简单

一个变量cur做结果，最开始cur随意指，然后
俩变量p1,p2分别指向l1,l2
外部排序
谁小，cur指向谁?
然后cur不断往下移
最后谁没了，转移另一个指针到cur

最开始cur指向-1
然后看看p1<=p2,看绿色那所以c指向p1，然后p1移动到橘色p1那，c移动到c的下一个位置，橘色c
然后看看p1>p2,所以c指向p2，然后p2移动到粉色p2那，c一移动到粉色c
然后看看p1<=p2,所以c指向p1，然后p1移动到蓝色p1那，c移动到c的下一个位置，蓝色c
然后看看p1>p2,所以c指向p2，然后p2移动到红色p2那，c一移动到红色c
然后看看p1<=p2,所以c指向p1，然后p1移动到null，c移动到c的下一个位置，紫色c

一旦p1,p2有一个是null，说明一条链表对比结束
将不null那个链表挂上c.next=p2完事，紫色那条线

自己不会就学习别人的做法
然后自己手撕，熟悉代码

//最优解：既可以省时间，又可以省空间public ListNode mergeTwoLists(ListNode l1, ListNode l2){//一个变量cur做结果，最开始cur随意指，然后ListNode ans = new ListNode(-1);//待会返回ans.nextListNode cur = ans;//俩变量p1,p2分别指向l1,l2ListNode p1 = l1;ListNode p2 = l2;//外部排序while (p1 != null && p2 != null){//谁小，cur指向谁?if (p1.val <= p2.val){cur.next = p1;p1 = p1.next;//不会断开的}else {cur.next = p2;p2 = p2.next;//不会断开的}//然后cur不断往下移cur = cur.next;}//最后谁没了，转移另一个指针到curif (p1 == null) cur.next = p2;else cur.next = p1;//p2为nullreturn ans.next;//-1开头}

测试一把：

    public static ListNode createList1(){ListNode l1 = new ListNode(1);ListNode l12 = new ListNode(2);ListNode l13 = new ListNode(4);l1.next = l12;l12.next = l13;return l1;}public static ListNode createList2(){ListNode l2 = new ListNode(1);ListNode l22 = new ListNode(3);ListNode l23 = new ListNode(4);l2.next = l22;l22.next = l23;return l2;}public static void test(){ListNode l1 = createList1();ListNode l2 = createList2();Solution solution = new Solution();ListNode res = solution.mergeTwoLists2(l1, l2);while (res != null){System.out.print(res.val + " ");res = res.next;}System.out.println();ListNode l3 = createList1();ListNode l4 = createList2();res = solution.mergeTwoLists(l3, l4);while (res != null){System.out.print(res.val + " ");res = res.next;}}public static void main(String[] args) {test();}

绝对屌爆了

1 1 2 3 4 4 
1 1 2 3 4 4 

代码非常简单，这个思路，自己记住了，非常非常非常简单

总结

提示：重要经验：

1）merge最简单的就是链表转数组，然后合并，外部排序，很容易。
2）实际上还有更简单的就是4个指针，同时控制往下走就完事
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。