【JS】链表中的节点每k个一组翻转

每K个一组。可以看成子问题，递归解决。

把问题分成两半，一半是我们要翻转手头上的K个节点，另一半是翻转后面的节点。

假设后面的节点已经翻转完毕，那么只需要把前K个翻转后的尾节点与 另一个半的头结点相连，然后返回当前的头结点，就可以了。

而关键的如何翻转后面的节点，就是递归，看成子问题了。

而翻转K个，相信大家也很熟悉。

/**
  * 
  * @param head ListNode类 
  * @param k int整型 
  * @return ListNode类
  */
function reverseKGroup( head ,  k ) {
  if (!head) return head;
  let a = head;
  let b = head;
  for (let i = 0; i < k; i++) {
    // 不满足 K 个一组，直接返回头结点
    if (!b) return head;
    b = b.next;
  }
  // 新的头结点
  let newHead = reverseLink(a, b);
  // 此时翻转后，a是尾节点了，与子问题的头结点相接即可
  a.next = reverseKGroup(b, k);
  // 返回头结点
  return newHead;
}

// [head, tail) 翻转
function reverseLink(head, tail) {
  let cur = head;
  let pre = null;
  let next = cur;
  while (cur !== tail) {
    next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
  }
  return pre;
}
module.exports = {
    reverseKGroup : reverseKGroup
};