时间轴

2025-11-20

init

题目：

P25 K 个一组翻转链表

https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-interview-150

链表的题目中一般不能直接更改结点的值。
使用头插法反转链表，创建一个虚拟头节点，指向第一组的第一个结点，但是到第二组时，要用第一组的尾结点作为虚拟头节点。否则反转第二组会破坏第一组的最后一个结点和第二组第一个结点的联系。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
struct ListNode {
	int val;
	ListNode *next;
	ListNode()
		: val(0)
		, next(nullptr)
	{
	}
	ListNode(int x)
		: val(x)
		, next(nullptr)
	{
	}
	ListNode(int x, ListNode *next)
		: val(x)
		, next(next)
	{
	}
};

class Solution {
    public:
	ListNode *reverseKGroup(ListNode *head, int k)
	{
		int i, j;
		ListNode *virt_head = new ListNode;
		virt_head->next = head;
		ListNode *group_tail;
		ListNode *res = head;
		ListNode *tmp, *p;

		for (i = 0; virt_head->next != nullptr; i++) {
			p = virt_head;
			group_tail = virt_head->next; //反转后下一组的前驱
			// 从virt_head开始往后走k个结点
			for (j = 0; j < k && p != nullptr; j++) {
				p = p->next;
			}

			if (p == nullptr) { // 最后一组不足k个
				break;
			}

			while (virt_head->next != p) {
				tmp = virt_head->next;
				virt_head->next = tmp->next;
				tmp->next = p->next;
				p->next = tmp;
			}
			if (i == 0) {
				res = virt_head->next;
				delete virt_head;
			}
			virt_head = group_tail;
		}

		return res;
	}
};