148. Sort List

문제 링크: https://leetcode.com/problems/sort-list/?envType=study-plan-v2&envId=top-interview-150

문제

연결 리스트의 head가 주어지면, 해당 연결리스트를 오름차순으로 정렬한 후, 반환하자

나의 풀이

접근

연결 리스트를 정렬할 때 고려할 점은 인덱스로 접근이 불가하다는 것이다.

그렇다면 여러 개의 pointer를 이용해 접근하면 될 것 같다는 생각이 들었고, 머지소트와 퀵정렬이 떠올랐다.

퀵 정렬은 각 요소 위치를 계속해서 스위칭하기 떄문에, 머지소트가 더 구현이 간편할거라 생각해, 머지소트로 구현해보려했다.

재귀함수를 이용해 구현하려 했지만, 너무 오랜 시간을 사용한 탓에 풀이를 보기로 결정했다.

---

다른 풀이

사실 이전에 내가 시도할 때에도, 연결리스트의 중간 지점을 어떻게 탐색해, 머지 소트를 이용할 것인지에 대해 막힌 점도 있었다.

하지만, 이 코드는 slow 와 fast 포인터를 이용해 효율적으로 중간 지점을 찾아 반을 나누어 머지 소트를 진행하고 있다.

public class Solution {
  
  public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
      return head;
        
    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;
    
    ListNode l1 = sortList(head);
    ListNode l2 = sortList(slow);

    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;
  }

}

• 우리가 아는 머지소트와 같이, fast 와 slow 포인터를 이용해 중간 지점을 찾아, 반으로 나눈다.
• 반으로 나눈 연결리스트는 각각 sortList() 함수를 재귀적으로 호출해, 더 이상 반으로 쪼개지지 않을 때까지 반복한다.
• 이후에 작은 부분부터 정렬해나가기 시작하고, 결국 전체의 반을 다시 합치는 과정을 통해 결국 정렬된 연결리스트의 head를 반환하게 된다.

합병정렬을 사용하기 때문에, 시간복잡도는 O(nlogn)을 가진다.

하지만, 재귀 자체는 아무것도 하지 않아도 메모리는 차지하기 때문에 공간 복잡도는 O(nlogn)이 된다고 할 수 있다.