148. Sort List

Link

Solution

這題要用mergeSort來做

1. 先將list切成兩半(透過fast, slow)，然後要把前一次slow的next設為null才能段的乾淨

2. 針對兩邊進行sort

3. merge兩邊sort結果

 public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;
        while(fast != null && fast.next != null){
            prev = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        
        prev.next = null;
        fast = head;
        ListNode node1 = sortList(slow);
        ListNode node2 = sortList(fast);
        return merge(node1, node2);
    }
    
    public ListNode merge(ListNode node1, ListNode node2){
        ListNode dummy = new ListNode(0);
        ListNode begin = dummy;
        while(node1 != null && node2 != null){
            if(node1.val > node2.val){
                dummy.next = node2;
                node2 = node2.next;
            }
            else{
                dummy.next = node1;
                node1 = node1.next;
            }
            dummy = dummy.next;
        }
        if(node1 != null){
            dummy.next = node1;
        }
        if(node2 != null){
            dummy.next = node2;
        }
        return begin.next;
    }