[자바스크립트] 연결리스트 & 병합정렬 문제 - Leet 148. Sort List

🔗 Leet 148. Sort List

Linked List 를 Merge Sort 로 정렬해서 풀이

🌱 1. 병합 정렬 구조로 나누기

1. 기본 병합 정렬 구조대로 나누되, 배열 대신 연결 리스트를 어떻게 절반을 쪼개고 합칠지가 관건이다.

var sortList = function(head) {
    if(!head || !head.next) return head // 요소가 1개 이하이면 그대로 리턴
    
    let [left, right] = splitList(head) // 2. 절반씩 쪼개는 함수 아래 후술
    let _left = sortList(left)
    let _right = sortList(right)

    return merge(_left, _right) // 3. 다시 합치는 함수 아래 후술
};

❓의문점 : 문제에서 주어진 Input의 head 가 배열의 형태의 전체 linked list 라고 생각했는데,
막상 head 는 linked list의 가장 첫번째 값을 가리키고 있었다.

Input: head = [4,2,1,3]
Output: [1,2,3,4]

빈 배열[]의 boolean 값은 true 인 것처럼
빈 linked list 도 true 라고 생각해서 if(!head.val || !head.next) return head 일거라고 생각했는데, head 가 null 이어서 null.val 를 읽을 수 없다는 에러가 발생했다.

🌱 2. left, right 절반씩 2개의 연결리스트로 나누기

배열의 경우 .length로 쉽게 전체 길이를 구해서 2로 나눠 절반씩 2개의 배열로 나눌 수 있지만,
연결리스트는 .next.next.next ... 가 어디까지 있을 지 길이를 알기 어렵다.

head 부터 1개씩 이동해서 right list의 첫번째 head가 될 rightHead 변수와
2개씩 건너뛰는 stepper2 변수를 만들어서 stepper2 변수가 끝에 도달하면 rightHead는 절반 지점에 온 거니까 rightHead 를 기점으로 앞 뒤로 나눈다.

각 변수들은 입력되는 head에서 참조 할당(복사)된 것이므로
rightHead의 직전 노드에서 연결을 끊고,
return 은 left 와 right 리스트의 각 head를 return하면 된다.

연결을 끊기 위해 leftTail 변수에 rightHead 변수가 next로 넘어가기 전 값을 할당해 준다

function splitList(head){
  let rightHead = head // 오른쪽 list의 시작 점
  let stepper2 = head // head의 끝까지 가서 while문을 멈추는 역할

  // 왼쪽 list의 시작점은 head
  let leftTail = null // 왼쪽 list 의 마지막 (= 오른쪽 list의 -1)

    while(stepper2 && stepper2.next){ // 두 칸씩 뛰어서 끝에 도달하는 시점 = rightHead가 전체 길이의 절반까지 이동
        leftTail = rightHead // 오른쪽 list의 바로 직전까지가 왼쪽 list의 마지막 노드
        rightHead = rightHead.next
        stepper2 = stepper2.next.next
    }

    leftTail.next = null // 왼쪽 list와 오른쪽 list를 분리

    return [head, rightHead]
}

🌱 3. 다시 하나의 연결리스트로 합치기

left 와 right 리스트의 각 첫번째 val 값을 비교하여 작은 값을 새로운 연결리스트에 모아서 리턴한다.

이때 새로운 연결리스트를 만들기 위해,
첫 번째 노드로 가짜 dummyNode를 만들고 그 next 에 left 와 rigt 중 작은 값을 연결한다.

function merge(left, right){
    
    let dummyNode = new ListNode(0, null)
    let current  = dummyNode

    while(true){
        if(left.val < right.val){
            current.next = left // 둘 중 작은 값을 next 값으로 연결한다
            current = current.next
          
            if(left.next){ 
                left = left.next
            } else{ // next가 없으면 left의 마지막 노드였으므로 그 뒤는 right 노드를 전부 연결해주고 반복문을 끝낸다
                current.next = right
                break
            }
          
        } else {
            current.next = right
            current = current.next
          
            if(right.next){
                right = right.next
            } else{
                current.next = left
                break
            }
        }     
    }
    return dummyNode.next // 첫번째 가짜 더미노드 다음을 head(시작점)로 하는 노드를 리턴한다
}