K个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

img

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

示例 2：

img

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

提示：

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

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

题目不难，就是涉及到的点很多容易绕晕。

直接看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode h = new ListNode();
        h.next = head; // 头结点
        ListNode p = head; // p是每一组链表的首元节点
        ListNode preP = h; // preP是每一组链表的头结点指向p
        while (p != null) {
            ListNode q = p; // q负责找到下一组链表的开头
            for (int i = 0; i < k; i++) {
                if (q != null) {
                    q = q.next;
                } else {
                    return h.next;
                }
            }
            ListNode newHead = null; // 逆置后的新首元节点
            ListNode t = null; // 用于链表逆置
            ListNode oldP = p; // 链表原首元节点位置
            while (p != q) {
                t = p.next;
                p.next = newHead;
                newHead = p;
                p = t;
            }
            preP.next = newHead;
            oldP.next = q;
            preP = oldP;
            p = q;
        }
        return h.next;
    }
}