LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 将链表不断拆分，然后两两合并即可

// 拆分过程如下
l = 4->2->1->3->5

l1 = 4->2
l2 = 1->3->5

l1.1 = 4
l1.2 = 2
12.1 = 1
l2.2 = 3->5

l1.1 = 4
l1.2 = 2
12.1 = 1
l2.2.1 = 3
l2.2.2 = 5

// 合并过程如下
l1 = 2->4
l2.1 = 1
l2.2 = 3->5

l1 = 2->4
l2 = 1->3->5

l = 1->2->3->4->5

• 要拆分链表，先要找到链表中点，利用快慢指针即可。快指针每次前进两步，慢指针每次前进一步，快指针到达链表尾部时，慢指针则位于链表中点

class Solution {
 public:
  ListNode* sortList(ListNode* head) {
    if (!head || !head->next) {
      return head;
    }
    ListNode* slow = head;
    ListNode* fast = head;
    ListNode* pre = slow;
    while (fast && fast->next) {
      pre = slow;
      slow = slow->next;
      fast = fast->next->next;
    }                     // slow现在位于链表中点
    pre->next = nullptr;  // 拆分后，slow 是第二个链表的头节点
    ListNode* l1 = sortList(head);
    ListNode* l2 = sortList(slow);
    return mergeTwoLists(l1, l2);
  }

  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) {
      return l2;
    }
    if (!l2) {
      return l1;
    }
    if (l1->val < l2->val) {
      l1->next = mergeTwoLists(l1->next, l2);
      return l1;
    }
    l2->next = mergeTwoLists(l2->next, l1);
    return l2;
  }
};