[75 LeetCode] 47 - Reorder List

[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.

블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

문제 링크: https://leetcode.com/problems/reorder-list/description/

Reorder List - LeetCode

 

# 풀이 1

풀이방법은 다음과 같다.

1. 기존 리스트의 반까지 갈 수 있는 헤드를 준비한다.
2. 그 이후의 노드 부터 reverse된 리스트를 가져올 수 있는 헤드를 준비한다.
3. 두 헤드를 순서대로 엮어준다.

로직보단 구현문제에 가까운 것 같다.
이 로직을 차근차근 구현했다.

var reorderList = function(head) {
  let cur = head;
  let prev = null;
  let length = 0;

  // 리스트의 길이 구하기
  while (cur) {
      prev = cur;
      cur = cur.next;
      length += 1;
  }

  cur = head;
  prev = null;
  let tmp = null;
  const turnPoint = Math.ceil(length / 2);

  for(let i = 0; i < turnPoint; i++) {
      prev = cur;
      cur = cur.next;
  }
  
  // 중간 이후로 reverse 시켜 reversed 헤드 구하기
  prev.next = null;
  let next = null;
  for (let i = turnPoint; i < length; i++) {
      next = cur.next;
      cur.next = tmp;
      tmp = cur;
      cur = next;
  }

  let reversed = tmp;
  cur = head;

  // 엮기
  for(let i = 0; i < Math.floor(length / 2); i++) {
      next = cur.next;
      cur.next = reversed;
      reversed = reversed.next;
      cur = cur.next;
      if (cur) {
          cur.next = next;
          cur = cur.next;
      }
  }
};

 

# 가장 빠른 풀이

풀이에서는 fast, slow 노드를 사용해서 반까지를 구한다.
fast는 두칸씩 전진, slow는 한칸씩 전진하면 마지막까지 갔을 때 slow가 가리키는 노드가 중간 노드이다.
이 포인트가 중요한 것 같다.

var reorderList = function(head) {
    var fast = head, slow = head;
    while (fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
    }
    
    var head2 = reverseList(slow.next);
    slow.next = null;
    merge(head, head2);
};

(reverse와 merge는 동일한 로직이므로 생략)