时间轴

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
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(0, 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;
	}
};

leetcode hot 100 rewrite

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
class Solution {
    private:
        ListNode *reverse_list(ListNode *head_prev, ListNode *tail_next)
        {
                ListNode *head = head_prev->next;
                ListNode *prev = tail_next, *curr = head, *next;

                while (curr != tail_next) {
                        next = curr->next;
                        curr->next = prev;
                        prev = curr;
                        curr = next;
                }
                head_prev->next = prev;
                return head; // next prev
        }

    public:
        ListNode *reverseKGroup(ListNode *head, int k)
        {
                if (head == nullptr || k <= 1)
                        return head;

                int i;
                ListNode *virtual_head = new ListNode(0, head);
                ListNode *head_prev = virtual_head; // 第一个节点的前面的那个节点
                ListNode *tail_next = head; // 最后一个节点的下一个节点

                while (tail_next != nullptr) {
                        for (i = 0; i < k; i++) {
                                if (tail_next != nullptr)
                                        tail_next = tail_next->next;
                                else
                                        break;
                        }
                        if (i != k) // 不足k个
                                break;

                        head_prev = reverse_list(head_prev, tail_next);
                        tail_next = head_prev->next;
                }

                head = virtual_head->next;
                delete virtual_head;
                return head;
        }
};