25.K个一组翻转链表

链接：25.K个一组翻转链表
难度：Hard
标签：递归、链表
简介：给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

题解 1 - javascript

• 编辑时间：2020-05-16
• 执行用时：96ms
• 内存消耗：37.7MB
• 编程语言：javascript
• 解法介绍：每 K 个进行截取翻转。

function listNodeLastNode(node) {
  let temp = node;
  if (temp === null) return null;
  while (temp.next !== null) temp = temp.next;
  return temp;
}
function listNodeReverse(node) {
  let newRoot;
  function _reverse(node, prevNode) {
    if (node.next !== null) _reverse(node.next, node);
    else newRoot = node;
    node.next = prevNode;
  }
  _reverse(node, null);
  return newRoot;
}
function listNodeLength(node) {
  let l = 0,
    temp = node;
  if (temp === null) return l;
  while (temp !== null) {
    l++;
    temp = temp.next;
  }
  return l;
}
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
  if (head === null) return null;
  let temp = head,
    num = k;
  const rootArr = [temp];
  while (temp !== null) {
    if (--num === 0) {
      const next = temp.next;
      temp.next = null;
      temp = next;
      num = k;
      rootArr.push(next);
    } else temp = temp.next;
  }
  const len = rootArr.length;
  let root, lastNode;
  for (let i = 0; i < len; i++) {
    if (i === len - 1) {
      if (listNodeLength(rootArr[i]) !== k) lastNode.next = rootArr[i];
      else lastNode.next = listNodeReverse(rootArr[i]);
    } else {
      if (i === 0) root = listNodeReverse(rootArr[i]);
      else lastNode.next = listNodeReverse(rootArr[i]);
      lastNode = listNodeLastNode(root);
    }
  }
  return root;
};

题解 2 - typescript

• 编辑时间：2021-03-06
• 执行用时：100ms
• 内存消耗：42.5MB
• 编程语言：typescript
• 解法介绍：递归。

function _reverseList(head: ListNode, count: number): ListNode | null {
  if (count === 1 || head.next === null) return head;
  const tail = head.next;
  const nextList = _reverseList(tail, count - 1);
  head.next = tail.next;
  tail.next = head;
  return nextList;
}
function reverseList(head: ListNode, count: number): ListNode | null {
  let temp: ListNode | null = head;
  let c = count;
  while (--c && temp) temp = temp.next;
  return temp ? _reverseList(head, count) : head;
}
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  const dummyHead = new ListNode(0, head);
  let temp: ListNode = dummyHead;
  while (temp !== null && temp.next !== null) {
    temp!.next = reverseList(temp.next!, k);
    let count = k;
    while (count-- && temp !== null) temp = temp.next!;
  }
  return dummyHead.next;
}