리트코드 - 148. Sort List

리트코드 - 148. Sort List

출처 - https://leetcode.com/problems/sort-list/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

연결 리스트의 head가 주어졌을 때, 이 연결 리스트를 오름차순으로 정렬하여 반환하세요.

 

의사코드

함수 sortList     if (head가 null 이거나 head의 다음노드가 null이면)        head 리턴     count = 0     currentNode를 head로 설정     반복문 시작 [currentNode이 null이 아니면]        currentNode의 다음노드를 currentNode로        count 에 +1 을 더함 // currentNode의 갯수를 세기 위함     반복문 종료     currentNode를 다시 head로 설정     중간인덱스(middleIdx) = count / 2     왼쪽(left) 노드를 만들어서 head로 설정     오른쪽(right) 노드를 만들어서 null로 설정     반복문 시작 [i = 0부터 middleIdx -1 까지]        currentNode의 다음노드를 currentNode로     반복문 종료     right노드를 currentNode의 다음 노드로 설정     currentNode.next를 null로 초기화     left노드를 다시 sortList에 넣어 재귀     right노드를 다시 sortList에 넣어 재귀     merge(left, right) 리턴 함수 끝 함수 merge(left, right)     dummyHead 노드를 값 1로 초기화     currentNode를 dummyHead로 설정     반복문 시작 [left가 null이 아니고, right가 null이 아니면]         if (left노드 값 < right노드 값)              currentNode를 left 노드로             left노드를 left 노드의 다음노드로                else             currentNode를 right 노드로             right노드를 right 노드의 다음노드로            반복문 종료     if (left 노드가 남아있으면)         currentNode의 다음 노드를 left로     else         currentNode의 다음 노드를 right로         dummyHead의 다음 노드 리턴 함수 끝

 

풀이코드

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        int count = 0;
        ListNode currentNode = head;
        while (currentNode != null) {
            currentNode = currentNode.next;
            count++;
        }
        currentNode = head;

        int middleIdx = count / 2;
        ListNode left = head;
        ListNode right = null;

        for (int i = 0; i < middleIdx - 1; i++) {
            currentNode = currentNode.next;
        }
        right = currentNode.next;
        currentNode.next = null;
        left = sortList(left);
        right = sortList(right);

        return merge(left, right);
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummyHead = new ListNode(0);
        ListNode currentNode = dummyHead;

        while (left != null && right != null) {
            if (left.val < right.val) {
                currentNode.next = left;
                left = left.next;
            } else {
                currentNode.next = right;
                right = right.next;
            }
            currentNode = currentNode.next;
        }
        if (left != null) {
            currentNode.next = left;
        } else {
            currentNode.next = right;
        }
        return dummyHead.next;
    }
}

코드설명

분할정복을 이용한 방법이다.

우선 head노드나 head노드의 다음 노드가 null 이면 정렬을 할 필요가 없으므로 바로 head를 리턴한다.

 

다음으로 count 변수를 생성하여 head 노드를 순회하며 갯수를 센다.

count / 2 하여 중간인덱스(middleIdx)를 찾고 left 노드와 right 노드를 만든다.

left노드의 출발은 head부터이고, right 노드의 출발은 middleIdx로 만들어 준다.

 

i=0에서 부터 i < middleIdx -1 까지 순회하며 currentNode를 계속 이동하여 currentNode의 다음을 right 노드로 바꿔주고,

currentNode를 null로 하여 left 노드가 middleIdx-1 까지만 순회하도록 해준다.

 

이후left 노드와 right 노드를 sortList 함수를 재귀를 사용하여 반복해주고, 이 left와 right를 merge함수로 더해준다.

 

merge함수에서는 새 노드를 만들어서

매개변수로 받은 left노드와 right 노드를 비교하여 작은 값을 새 노드에 넣고 다음 노드로 이동하는 것을 반복해준다.

 

이렇게 반복하면 마지막 남는 노드가 생기는데, 이 노드를 추가해주고 새 노드를 리턴한다.

 

글로 적으니 상당히 복잡한데 나중에 그림으로 다시 적어서 표현해봐야겠다.

 

시간복잡도 - O(n * log n)

공간복잡도 - O(n) 노드 갯수만큼

 

문제를 풀며 생각한 흐름과 배운 점

노드를 다루는 것이 익숙하지 않아 다음 노드와 현재 노드 어떤 것부터 바꿔줘야 하는지 몹시 헷갈렸다.

그리고 코드가 너무 길어져서 이 방법이 맞는지 계속 고개를 갸우뚱 해야했다.

차라리 배열에 적용한다면 쉽게 할 텐데, 노드를 사용하라고 하니 막막했던 부분이 컸다.

 

다른 사람 코드에서 배워봐야겠다.

 

다른코드

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

}

위 코드가 내 것과 큰 차이점은 따로 count를 두지 않고, 그냥 속도차이가 나는 노드 두개를 보낸다는 것이다.

이전에 LinkedList를 확인하는 문제에서 사용한 토끼와 거북이 알고리즘과 비슷하다.

 

이전 문제에서는 토끼가 거북이를 만난다면 LinkedList였다면, 이번에는 토끼가 도착하면 거북이는 중간값을 가지는 것이다.

이렇게 하니 내 코드처럼 count를 안써서 코드가 다소 줄어들었다.

 

그렇지만 기본적인 생각은 동일했던 것 같다.

너무 고민을 오래해서 이러한 방법이 있다는 것을 한 번이라도 본적이 있었다면, 잊지 않고 써먹었을텐데하는 아쉬움이 든다.

 

정리

노드의 중간값을 찾을때는 속도가 다른 두개의 노드를 사용하기