25. Reverse Nodes in k-Group

source: https://leetcode.com/problems/reverse-nodes-in-k-group/

Question

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

思路

这套题其实思路会很清晰，就是基于206题去翻转数组。但是对于具体设计，要写对有相当的难度。

这题巧妙的地方在于，引入了一个dummy head，统一操作，不用考虑特殊情况，大大减小了复杂度。

const reverseList = (head, tail) => {
  let prev = tail.next;
  let crr = head;
  while (prev !== tail) {
    const next = crr.next;
    crr.next = prev;
    prev = crr;
    crr = next;
  }
  return [tail, head];
};
var reverseKGroup = function (head, k) {
  const dummyHead = new ListNode(0, head);
  let prev = dummyHead;
  while (head) {
    let tail = prev;
    for (let i = 0; i < k; i++) {
      tail = tail.next;
      if (!tail) return dummyHead.next;
    }
    const next = tail.next;
    [head, tail] = reverseList(head, tail);
    prev.next = head;
    tail.next = next;
    prev = tail;
    head = tail.next;
  }
  return dummyHead.next;
};

End

对于基础操作要极为熟练，遇到提高题的时候再运用一点技巧，才可以快速解题。