题解 | #链表中的节点每k个一组翻转#

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 *
 * @param head ListNode类
 * @param k int整型
 * @return ListNode类
 */

// 思路：发现大量重复类似的代码，所以递归调用
function reverseKGroup(head, k) {
  if (k == 1 || head == null) {
    return head;
  }
//  变量说明，pre、cur,逆序操作的双指针，newHead、newEnd，逆序操作之后的新的链头，链尾
  let newHead = null;
  let newEnd = null; 
  let pre = null;
  let cur = head;
//     判断当前一组是否长度小于k，如果是就返回head，这里的head实际上是递归传入的head，除了第一组之外，其实都是newHead
  let tmpCur = cur;
  for (let i = 0; i < k; i++) {
    if (tmpCur == null) {
      return head
    }
    tmpCur = tmpCur.next;
  }
  for (let i = 0; i < k; i++) {
    if (i == 0) {
      newEnd = cur;
// 这里保存一这一组的开头，执行完下面的逆序之后这里就变成了链尾，需要设定他的next为下一组的newHead
    }
//  逆序操作的代码
    let nextNode = cur.next;
    cur.next = pre;
    pre = cur;
    cur = nextNode;
  }
//  找到逆序之后的链头
  newHead = pre;
  if (cur != null) {
//   此时的cur进入了下一组的链头(未逆序操作的)，判断是否递归，此时递归的head是当前的cur。这个递归返回的是那一段的新链头，需要将本段的链尾指向下一段的链头（将一段段的子链表，连接起来）
    newEnd.next = reverseKGroup(cur, k);
  }
//  返回新的链头
  return newHead;
}

module.exports = {
  reverseKGroup: reverseKGroup,
};