合并两个链表c++_21 合并两个有序链表

朴灿烈づ我的快乐病毒、 2022-10-25 04:52 219阅读 0赞

###  ###

# 01 #

题目信息

> 题目地址: 
> 
> https://leetcode-cn.com/problems/merge-two-sorted-lists/

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

**示例：**

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

###  ###

# 02 #

解法一：迭代

两个链表两个指针不停的比较拼接新链表直到都遍历完成，每个迭代四个变动(三个指针以及cur指针的next)

![98748db828458b94cdca471cea07781a.gif][]

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {     ListNode head = new ListNode(0);     ListNode cur = head;     while (l1 != null && l2 != null) {         if (l1.val <= l2.val) {             cur.next = l1;             l1 = l1.next;         } else {             cur.next = l2;             l2 = l2.next;         }         cur = cur.next;     }     //处理最后的，另一个链表无论还剩多少个都是排好序的并且比当前大直接拼在当前之后就好     cur.next = l1 == null ? l2 : l1;     return cur.next; }

###  ###

# 02 #

解法二：递归

同样的改递归自顶向上，到l1/l2为null时才完成全部，那么他就是我们的递归出口，除此之外循环迭代最后一步也就是比大小设置指向。这样去想如果l1.next与l2已完成顺序合并，那么l1改指向谁呢？

![93518b645d094410d10e42540f80351e.png][]

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {     if (l1 == null) return l2;     else if (l2 == null) return l1;     //谁是头     if (l1.val         l1.next = mergeTwoLists(l1.next, l2);         return l1;     } else {         l2.next = mergeTwoLists(l1, l2.next);         return l2;     } }

###  ###

# 03 #

总结

也是比较简单并且与前几道题一样仍然是迭代调整同样也可以转一下递归

[98748db828458b94cdca471cea07781a.gif]: /images/20221024/d5fc159cfc084ebc907b39ee28b99e2e.png
[93518b645d094410d10e42540f80351e.png]: /images/20221024/c5a3c6486d8a4a75a9da8f67e0cd4482.png