[Linked List][Medium] 148. Sort List

Q. 주어진 리스트를 오름차순 정렬하라. 

 이때 정렬시간을 O(nxlogn) 으로 하여라. 

 

Solution. 

 분할 정렬 하라는 것이다. 

 분할 병합 정렬을 하기 위한 방법을 정리 해 본다. 

 우선 list를 2개로 계속 나눈다.

 리스트가 하나의 노드만 가질때까지 계속 쪼갠다. 

 이후로 작은 것 먼저 이어서 위로 반환한다. 

 분할 조립이 분할/순차적으로 되어야 하므로, 재귀함수가 필요하다. 

 

 로직대로 코드를 만든다. 

 

 

public ListNode SortList(ListNode node) 
{
    // 1개의 노드(이하)가 되면, 그냥 반환한다.
    if(node == null)        return null;
    if(node.next == null)   return node;

    // break list.
    ListNode fast = node;
    ListNode slow = node;
    ListNode prev = null;
    while(fast!=null && fast.next!=null)
    {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 분할 후 실제로 리스트를 끊는다.
    if(prev!=null) prev.next = null;

    // 전반부, 후반부 나누워 병합정렬한다.
    ListNode first = SortList(node);
    ListNode second = SortList(slow);

    node = null;
    prev = null;
    // 작은 순서대로 리스트에 잇는다.
    while(first!=null || second!=null)
    {
        int firstV = first!=null ? first.val : int.MaxValue;
        int secondV = second!=null ? second.val : int.MaxValue;

        ListNode cur = null;
        if(firstV > secondV)
        {
            cur = second;
            second = second.next;
        }
        else
        {
            cur = first;
            first = first.next;
        }

        if(node == null)
            node = cur;

        if(prev != null)
            prev.next = cur;

        prev = cur;
    }
    return node;
}

 

 

성능은 그닥이지만, 로직은 대동소이 하다.