[ Top Interview 150 ] 148. Sort List

문제

148. Sort List

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

• Input : singly-linked list의 head node
• Output : linked list를 오름차순으로 정렬 후, head node 반환

알고리즘 전략

• linked list (?)

  • 단순한 array를 통한 Sorting 이었으면 다양한 방법을 생각해 보았을 것 같은데, linked list에 어울리는 Sorting 방법에 대해서 고민했다.
  • 너무 큰 거시적인 관점에서만 생각하다보니 잘 안되서, 간단한 방법부터 구현해보기로 했다.

• 방법 1. Insertion Sort

  • 뒤의 Node부터 정렬해나간다.
  • head Node를 뒤의 정렬된 노드 사이에 삽입하는 과정을 재귀적으로 반복한다
  • Time complexity : $O(n^2)$

• 방법 2. Marge Sort 일부 변형

  • 기존의 Marge Sort는 절반씩 나눈 후에 각각을 Sorting 하는 방법을 재귀적으로 사용한다.
  • Linked List를 절반으로 나눌 방법이 생각나지 않아, 일단 Node 하나씩 나누고 합쳐가는 방법을 사용하기로 했다.
  • Time complexity : $O(nlogn)$

방법 1. Insertion Sort

• head Node를 뒤의 정렬된 노드 사이에 삽입하는 과정을 재귀적으로 반복한다
• Time complexity : $O(n^2)$

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) { // 예외 처리 (0개, 1개)
            return head;
        }

        ListNode beforeHead = sortList(head.next); // 뒤의 노드 정렬
        
        if (head.val < beforeHead.val) { // head가 더 작으면
            head.next = beforeHead;
            return head;
        }
        
        ListNode beforeCurNode = beforeHead;
        ListNode curNode = beforeHead.next;
        while (curNode != null && head.val > curNode.val) { // 중간 삽입 위치 찾기
            beforeCurNode = curNode;
            curNode = curNode.next;
        }

        beforeCurNode.next = head; // 중간 노드 사이에 들어가기
        head.next = curNode;
        return beforeHead;
    }
}

방법 2. Marge Sort 변형

• 알고리즘 과정
  • 각각의 Node를 전부 Queue에 집어 넣는다.
  • Queue에서 두 Node를 꺼낸 후에 오름차순으로 정렬 후 head node를 다시 Queue에 집어넣는다.
  • Queue의 원소가 하나가 될때까지 반복한다.
  • Queue에 마지막 원소가 정렬된 linked-list의 head node가 된다.
• Time complexity : $O(nlogn)$

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }

        Queue<ListNode> queue = new LinkedList<>();

        ListNode inputNode = head;
        while (inputNode != null) {
            ListNode nextInputNode = inputNode.next;
            queue.add(inputNode);
            inputNode.next = null;
            inputNode = nextInputNode;
        }

        while (queue.size() > 1) {
            ListNode sortListNode = sortTwoSortedListByOne(queue.remove(), queue.remove()); 
            queue.add(sortListNode);
        }

        return queue.remove();
    }

    private ListNode sortTwoSortedListByOne(ListNode node1, ListNode node2) {
        ListNode head = node1;
        if (node1.val <= node2.val) {
            node1 = node1.next;
        } else {
            head = node2;
            node2 = node2.next;
        }
        
        ListNode beforeNode = head;
        ListNode currentNode;
        while (node1 != null || node2 != null) {
            
            if (node1 == null) {
                currentNode = node2;
                node2 = node2.next;
            } else if (node2 == null) {
                currentNode = node1;
                node1 = node1.next;
            } else if (node1.val <= node2.val) {
                currentNode = node1;
                node1 = node1.next;
            } else {
                currentNode = node2;
                node2 = node2.next;
            }
            
            beforeNode.next = currentNode;

            beforeNode = currentNode;
            currentNode = null;
        }
        
        return head;
    }
}

모범 답안 Marge Sort 이용

• Marge Sort 이용 방법

  • 하나의 linked-list를 절반으로 나누는 과정을 Floyd's Cycle Detection Algorithm을 이용했다.
  • 그 다음 두 linked-list를 합쳐나가서 하나의 linked-list를 만들었다.

• Floyd's Cycle Detection Algorithm

  • linked list에서 한 칸씩 이동하는 포인터(slow), 두 칸씩 이동하는 포인터(fast)를 이용한다.
  • 주로 해당 linked list가 순환하는지 알아보기 위한 용도로 사용된다.
    • slow, fast가 같은 객체를 가리키게 되면 해당 linked list가 순환한다.
  • 현 상황에서는 하나의 linked list를 반으로 나누는 방법으로 사용되었다.

public class Solution {
  
  public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
      return head;
        
    // step 1. cut the list to two halves
    ListNode prev = null, slow = head, fast = head;
    
    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);
  }
  
  ListNode merge(ListNode l1, ListNode l2) {
    ListNode l = new ListNode(0), p = l;
    
    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 l.next;
  }

}