148. 排序链表

image.png
归并排序

  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.     // 合并两个升序链表
  14.     ListNode* merge(ListNode* h1, ListNode* h2) {
  15.         if (!h1) return h2;
  16.         if (!h2) return h1;
  17.         ListNode* dummy = new ListNode();
  18.         ListNode* cur = dummy;
  19.         while (h1 && h2) {
  20.             if (h1->val < h2->val) {
  21.                 cur->next = h1;
  22.                 h1 = h1->next;
  23.             } else {
  24.                 cur->next = h2;
  25.                 h2 = h2->next;
  26.             }
  27.             cur = cur->next;
  28.         }
  29.         cur->next = h1 ? h1 : h2;
  30.         return dummy->next;
  31.     }
  32.     ListNode* sortList(ListNode* head) {
  33.         if (head == nullptr || head->next == nullptr) return head;
  34.         // 通过快慢指针将链表分割为两部分
  35.         ListNode* left = head;
  36.         ListNode* mid = head->next;
  37.         ListNode* right = head->next->next;
  39.         while (right && right->next) {
  40.             right = right->next->next;
  41.             left = left->next;
  42.             mid = mid->next;
  43.         }
  44.         left->next = nullptr;
  45.         return merge(sortList(head), sortList(mid));
  46.     }
  47. };

23. 合并K个升序链表

image.png
归并

// 归并
class Solution {
public:
    ListNode* merge(ListNode* head1, ListNode* head2) {
        if (head1 == nullptr) return head2;
        if (head2 == nullptr) return head1;
        ListNode head, *cur = &head, *l1 = head1, *l2 = head2;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1 ->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if (!l1) cur->next = l2;
        if (!l2) cur->next = l1;
        return head.next;
    }

    ListNode* mergeK(vector<ListNode*>& lists, int l, int r) {
        if (l > r) return nullptr;
        if (l == r) return lists[l];
        int mid = (l + r) >> 1;
        return merge(mergeK(lists, l, mid), mergeK(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return nullptr;
        return mergeK(lists, 0, lists.size() - 1);
    }
};