/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    
    // Merge Sort: 두파트로 나누어서 각각 정렬하고 병합한다.
    // T: O(n*logn)
    public ListNode sortList(ListNode head) {
        // 종료조건
        if (head == null || head.next == null) {
            return head;
        }

        // step 1. split the list into two halfs
        ListNode slow = head, fast = head;
        
        // 왼쪽 마지막 노드
        ListNode prev = null;

        // 중앙 노드를 찾는다.
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        // * 왼쪽 마지막 노드의 링크를 널로 만든다(아니면 무한루프에 빠지게 된다).
        prev.next = null;

        // step 2. sort each half
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);

        // step 3. merge l1 and l2
        return merge(l1, l2);
    }

    // 두 리스트를 정렬하면서 병합한다.
    // O(n)
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        
        // 현재노드 포인터
        ListNode p = dummy;

        // 작은 노드를 P 노드에 연결 시킨다.
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }

        if (l1 != null) p.next = l1;
        if (l2 != null) p.next = l2;

        return dummy.next;
    }
}