PattySung

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

<解題>

用merge sort 的方式，所以要先找出中間點，把一個array一分為二，故先建立temp, slow, fast 三個指標
while迴圈中，slow 指針每次移動一步，fast 指針每次移動兩步，當 fast 指針達到連結串列的尾端時，slow 指針剛好指向中間節點
將連結串列拆分為兩部分，left_side 是原始連結串列的前半部分(left_side: head->…->temp)，right_side 是原始連結串列的後半部分(right_side: slow->…fast)
對 left_side（head) 和 right_side(slow) 分別遞迴調用 sortList 函式
最後，將排好序的merge(left_side, right_side)返回
merge 方法：用於合併兩個已排序的連結串列。使用兩個指針 l1 和 l2 分別指向兩個已排序連結串列的頭節點


class Solution {
    public ListNode sortList(ListNode head) {
        if(head ==null || head.next ==null) return head;

        ListNode temp = head;
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null){
            temp = slow;
            slow = slow.next;
            fast = fast.next.next; 
        }
        temp.next = null; 
        
        ListNode left_side = sortList(head);  //left_side: head->...->temp
        ListNode right_side = sortList(slow); //right_side: slow->...fast

        return merge(left_side, right_side);
    }

    public ListNode merge(ListNode l1, ListNode l2){
        ListNode sorted_temp = new ListNode(0);
        ListNode current_node = sorted_temp;

        while(l1!= null && l2 != null){
            if(l1.val < l2.val){
                current_node.next = l1;
                l1 = l1.next;
            } else{
                current_node.next = l2;
                l2 = l2.next;
            }
            current_node = current_node.next;
        }
        //當另外一個list為null，直接接完
        if(l1!= null){
            current_node.next = l1;
            l1 = l1.next;
        }
        if(l2!= null){
            current_node.next = l2;
            l2 = l2.next;
        }
        return sorted_temp.next;
    }
}

Time: O(n log n) Space: O(n)

Leetcode-148. Sort List

<解題>