21. 合并两个有序链表

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

示例 1：
链表3-合并问题 - 图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 均按 非递减顺序 排列
    1. class Solution {
    2. public:
    3.   ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    4.       if(l1 == nullptr){
    5.           return l2;
    6.       }else if(l2 == nullptr){
    7.           return l1;
    8.       }
    9.       if(l1->val < l2->val){
    10.           l1->next = mergeTwoLists(l1->next, l2);
    11.           return l1;
    12.       }else{
    13.           l2->next = mergeTwoLists(l1, l2->next);
    14.           return l2;
    15.       }
    16.   }
    17. };

    23. 合并K个升序链表

    难度困难1219
    给你一个链表数组，每个链表都已经按升序排列。
    请你将所有链表合并到一个升序链表中，返回合并后的链表。

    示例 1：
    输入：lists = [[1,4,5],[1,3,4],[2,6]]
    输出：[1,1,2,3,4,4,5,6]
    解释：链表数组如下：
    [
    1->4->5,
    1->3->4,
    2->6
    ]
    将它们合并到一个有序链表中得到。
    1->1->2->3->4->4->5->6

示例 2：
输入：lists = []
输出：[]

示例 3：
输入：lists = [[]]
输出：[]


提示：

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列

  • lists[i].length 的总和不超过 10^4

    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode() : val(0), next(nullptr) {}
    7. *     ListNode(int x) : val(x), next(nullptr) {}
    8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. * };
    10. */
    11. class Solution {
    12. public:
    13.   ListNode* mergeTwoLists(ListNode* a, ListNode* b){
    14.       if((!a) || (!b)) return a ? a : b;
    15.       ListNode* nhead = new ListNode(-1);
    16.       ListNode* pre = nhead;
    17.       ListNode* ap = a, *bp = b;
    18.       while(ap && bp){
    19.           if(ap->val < bp->val){
    20.               pre->next = ap;
    21.               ap = ap->next;
    22.           }else{
    23.               pre->next = bp;
    24.               bp = bp->next;
    25.           }
    26.           pre = pre->next;
    27.       }
    28.       pre->next = ap == nullptr ? bp : ap;
    29.       return nhead->next;
    30.   }
    31.   ListNode* merge(vector<ListNode*>& lists, int l, int r){
    32.       //只有一个元素的情况
    33.       if(l == r) return lists[l];
    34.       if(l > r) return nullptr;
    35.       int mid = l + r >> 1;
    36.       return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    38.   }
    39.   ListNode* mergeKLists(vector<ListNode*>& lists) {
    40.       return merge(lists, 0, lists.size() - 1);
    41.   }
    42. };

    148. 排序链表

    难度中等1058
    给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
    进阶：

  • 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？


    示例 1：
    链表3-合并问题 - 图2
    输入：head = [4,2,1,3]
    输出：[1,2,3,4]

示例 2：
链表3-合并问题 - 图3
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：
输入：head = []
输出：[]


提示：

  • 链表中节点的数目在范围 [0, 5 * 10] 内
  • -10 <= Node.val <= 10
    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode() : val(0), next(nullptr) {}
    7. *     ListNode(int x) : val(x), next(nullptr) {}
    8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. * };
    10. */
    11. class Solution {
    12. public:
    13.   ListNode* sortList(ListNode* head) {
    14.       return sortList(head, nullptr);
    15.   }
    16.   ListNode* sortList(ListNode* head, ListNode* tail){
    17.       if(head == nullptr){
    18.           return head;
    19.       }
    20.       if(head->next == tail){
    21.           head->next = nullptr;
    22.           return head;
    23.       }
    24.       //寻找中点
    25.       ListNode* slow = head, *fast = head;
    26.       while(fast != tail){
    27.           slow = slow->next;
    28.           fast = fast->next;
    29.           if(fast != tail){
    30.               fast = fast->next;
    31.           }
    32.       }
    33.       return merge(sortList(head, slow), sortList(slow, tail));
    34.   }
    35.   ListNode* merge(ListNode* l1, ListNode* l2){
    36.       if(!l1) return l2;
    37.       if(!l2) return l1;
    38.       ListNode* p1 = l1, *p2 = l2;
    39.       ListNode* dum = new ListNode(-1);
    40.       ListNode* p = dum;
    41.       while(p1 && p2){
    42.           if(p1->val <= p2->val){
    43.               p->next = p1;
    44.               p1 = p1->next;
    45.           }else{
    46.               p->next = p2;
    47.               p2 = p2->next;
    48.           }
    49.           p = p->next;
    50.       }
    51.       p->next = p1 == nullptr ? p2 : p1;
    52.       return dum->next;
    53.   }
    54. };