题解 | #单链表的排序#

链表也可以用归并！学到了

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
  public:
    ListNode* sortInList(ListNode* head) {
      if (head == nullptr || head->next == nullptr) {
        return head;
      }
      ListNode *left = head, *mid = head->next, *right = head->next->next;
      
      while (right && right->next) {
        left = left->next;
        mid = mid->next;
        right = right->next->next;
      }
      
      left->next = nullptr;
      
      return merge(sortInList(head), sortInList(mid));
    }
  private:
    ListNode *merge(ListNode *l1, ListNode *l2) {
      if (l1 == nullptr || l2 == nullptr) {
        return l1 == nullptr ? l2 : l1;
      }
      
      ListNode *head = l1->val < l2->val ? l1 : l2;
      ListNode *cur_head = head;
      l1 = head == l1 ? l1->next : l1;
      l2 = head == l2 ? l2->next : l2;
      
      while (l1 && l2) {
        cur_head->next = l1->val < l2->val ? l1 : l2;
        cur_head = cur_head->next;
        l1 = cur_head == l1 ? l1->next : l1;
        l2 = cur_head == l2 ? l2->next : l2;
      }
      
      cur_head->next = l1 ? l1 : l2;
      
      return head;
    }
};