25. Reverse Nodes in k-Group

문제링크: https://leetcode.com/problems/reverse-nodes-in-k-group/

노드의 k번째마다 순서를 뒤집는 문제다. O(1)의 추가 공간복잡도를 만족해야 한다.

Solution

Iteration with reverse function

스택을 이용하면 reverse를 간단하게 구현할 수 있지만,O(1)의 공간복잡도를 만족하기 위해서는 동적 포인터를 이용해 reverse를 구현해야 한다. reverse함수를 만든 후 반복을 통해 노드를 순회하고 count를 세며 k번째 노드를 만났을 경우 reverse를 실행한다.

Algorithm

• reverse함수는 뒤집을 노드의 바로 앞left와 노드의 끝end를 인자로 받는다.
• left의 다음을cur로 지정하고 cur.next를 추가로 저장한다.(다음반복을 위한 노드)
• cur이 loopEnd가 아닐 때까지 cur를 right(오른쪽 노드)에 연결하는 것을 반복한다.
• 모두 연결한 후 left와 end를 연결한다.(reverse완성)
• 위 과정을 노드를 순회하면서 count를 늘리고 k번째마다 실행한다.

var reverseKGroup = function(head, k) {
  // left와 end를 기준으로 reverse
  const reverse = (left, end) => {
    const result = left.next;
    let right = end.next;
    const loopEnd = right;
    let cur = left.next;
    while (cur !== loopEnd) {
      const next = cur.next;
      cur.next = right;
      right = cur;
      cur = next;
    }
    // 
    left.next = end;
    return result;
  }
  
  if (k === 1) return head;
  const dummy = new ListNode(0, head);
  
  let nodeStart = dummy;
  let curNode = dummy.next;
  let count = 1;
  while (curNode) {
    if (count === k) {
      curNode = reverse(nodeStart, curNode);
      nodeStart = curNode;
      count = 0;
    }
    count++;
    curNode = curNode.next;
  }
  return dummy.next;
};