148. Sort List

[fockspaces]

https://leetcode.com/problems/sort-list/description/

[fockspaces]

這裡我用

1. 快慢指針找中點（並切斷中間連接）
2. mergeSort 來拆分 case
3. merge 來形成有序 list

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return mergeSort(head);
    }

    ListNode* mergeSort(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* mid = middle(head);
        ListNode* left = mergeSort(head);
        ListNode* right = mergeSort(mid);
        return merge(left, right);
    }

    ListNode* middle(ListNode* head) {
        ListNode *slow = head, *fast = head->next;
        while(fast && fast->next) {
            slow = slow->next; fast = fast->next->next;
        }
        ListNode* middle = slow->next;
        slow->next = NULL;
        return middle;
    }

    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode();
        ListNode* cur = head;
        while(l1 && l2) {
            if(l1->val < l2->val) {cur->next = l1; l1 = l1->next;}
            else {cur->next = l2; l2 = l2->next;}
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return head->next;
    }
};