148. Sort List (Java, Merge Sort, Leetcode)

시간복잡도는 divide 하는데 O(n)

merge 하는데 O(nlogn)으로 O(n) + O(nlogn)이므로 O(nlogn).

다만 공간복잡도는 O(logn)으로 O(1)인 풀이방법도 있었지만 적용하기에 너무 복잡하다고 판단했다.

 

크게 base cases를 처리하는 부분

middle node를 구하고 divide하는 부분.

divide들을 merge하는 부분으로 나눌 수 있다.

 

/**
 * 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 {
    public ListNode sortList(ListNode head) {
    	//base cases 처리.
        if (head == null || head.next == null) return head;
        
        //middle node 구하기
        ListNode mid = getMid(head);
        
        //recursion으로 divide. 여기서 공간 복잡도가 O(logn)
        ListNode left = sortList(head);
        ListNode right = sortList(mid);
        
        //merge.
        return merge(left, right);
    }
    ListNode getMid(ListNode head) {
    	//중간값을 가르킬 pointer 선언.
        ListNode mid = null;
        
        //head pointer가 마지막에 도달했을때 mid pointer는 중간에 도달.
        while (head != null && head.next != null) {
            mid = mid == null ? head : mid.next;
            head = head.next.next;
        }
        //mid pointer의 다음 값을 저장한다. 
        //중간값의 그 다음값이 두번째 divide의 head이기때문.
        ListNode temp = mid.next;
        //next를 null로 지정하면서 2개의 divide가 생성됨.
        mid.next = null;
        //2번째 divide의 head를 리턴.
        return temp;
    }
    ListNode merge(ListNode left, ListNode right) {
    	//sorting 이후에는 list의 순서와 head를 모르기에 확실히 알고있는 값 하나를 선언.
        ListNode dummy = new ListNode(0);
        //dummy는 head로 쓰이고 pointer로 쓰일 mover에 head값 넣어줌.
        ListNode mover = dummy;
        
        //이미 sorting이 완료되어 있기때문에 둘 중 하나만 merge가 끝나도 됨.
        while (left != null && right != null) {
        	//두 divide를 비교 후 더 작은 값을 next에 넣고 pointer 이동.
            if (left.val < right.val) {
                mover.next = left;
                left = left.next;
            } else {
                mover.next = right;
                right = right.next;
            }
            //비교 이후에는 반드시 값이 들어가있으므로 mover pointer 이동.
            mover = mover.next;
        }
        //merge가 끝나고 나서도 남아있는 값을 그대로 next에 주입.
        //이미 sorting이 되어있어서 바로 넣어도 된다.
        mover.next = left == null ? right : left;
        
        //dummy는 다음 위치만 알고있는 node이므로 next부터 시작.
        return dummy.next;
    }
}