K 个一组翻转链表

题目描述

给你链表的头节点 head，每 k 个节点一组进行翻转，请你返回修改后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

示例 1： 输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2： 输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

思路&js代码

1、模拟

var reverseKGroup = function (head, k) {
  const start = new ListNode(0)
  start.next = head
 
  let prev = start
 
  while (head) {
    let tail = prev
    // 查看剩余部分长度是否大于等于 k
    for (let i = 0; i < k; ++i) {
      tail = tail.next
      if (!tail) {
        return start.next
      }
    }
    const tmp = tail.next
    ;[head, tail] = reverse(head, tail)
    // 把子链表重新接回原链表
    prev.next = head
    tail.next = tmp
 
    prev = tail
    head = tail.next
  }
  return start.next
}
 
// 翻转
function reverse(head, tail) {
  let prev = tail.next
  let curr = head
 
  while (prev !== tail) {
    const tmp = curr.next
    curr.next = prev
 
    prev = curr
    curr = tmp
  }
 
  return [tail, head]
}

2、迭代

var reverseKGroup = function(head, k) {
    // 统计节点个数
    let n = 0;
    for (let cur = head; cur; cur = cur.next) {
        n++;
    }
 
    const dummy = new ListNode(0, head);
    let p0 = dummy;
    let pre = null;
    let cur = head;
 
    // k 个一组处理
    for (; n >= k; n -= k) {
        for (let i = 0; i < k; i++) { // 同 92 题
            const nxt = cur.next;
            cur.next = pre; // 每次循环只修改一个 next，方便大家理解
            pre = cur;
            cur = nxt;
        }
 
        // 见视频
        const nxt = p0.next;
        p0.next.next = cur;
        p0.next = pre;
        p0 = nxt;
    }
    return dummy.next;
};