143. Reorder List

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

주어진 조건대로 연결 리스트를 재배열한다.

Solution

Stack and Insert

slow, fast 노드를 이용해 가운데 노드를 구하고 중간부터의 노드를 stack에 쌓는다. stack에는 가장 마지막 값부터 중간값까지 꺼낼 수 있게 되고 앞부터 2, 4, 6, ... 짝수 인덱스에 순서대로 삽입한다면 결과를 얻을 수 있다.

Algorithm

• slow, fast 노드를 사용해 mid Node를 구한다.
• mid Node 다음부터 끝까지의 노드를 stack에 push한다.
• 다시 노드의 처음으로 돌아와 stack에서 pop한 노드들을 짝수번째에 삽입한다.

var reorderList = function(head) {
  // Get half then stack and insert
  
  // 1. Get middle with slow & fast node
  let slow = head, fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // Slow node is middle node
  
  // Push remaining nodes to stack 
  const stack = [];
  let temp = slow.next;
  slow.next = null;
  while (temp) {
    stack.push(temp);
    temp = temp.next;
  }
  
  // Pop node and insert to even order
  let cur = head;
  while (stack.length > 0) {
    const toInsert = stack.pop();
    const prev = cur;
    cur = cur.next;
    prev.next = toInsert;
    toInsert.next = cur;
  }
  return head;
};

총 O(n) 의 시간복잡도를 가지며 단순히 모든 노드를 전부 배열에 넣고 앞뒤로 빼서 연결하는 방식보다 공간을 반만 쓰는 이득을 볼 수 있다. 뒷 부분을 stack을 이용하지 않고 reverse한 후 merge하는 방식으로도 구현할 수 있다.