Leetcode-25.K个一组翻转链表

Leetcode
1.2k 词

核心还是掌握链表的反转

image.png

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
# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, val=0, next=None):

#         self.val = val

#         self.next = next

class Solution:

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

        dummy=ListNode(0,head)

        pre=dummy


        while True:

            end =pre

            for _ in range(k):

                end=end.next

                if not end:

                    return dummy.next

            start=pre.next

            next_group=end.next

            cur=start

            prev=next_group

            while cur!=next_group:

                nxt=cur.next

                cur.next=prev

                prev=cur

                cur=nxt

            pre.next=end

            pre=start
  
        return dummy.next

1. 整条链表反转（一次性从头到尾）

经典的三指针法：

  • prev：保存反转后部分的头（初始为 None）

  • curr：当前正在处理的节点

  • next（或 nxt）：提前保存 curr.next，防止链表断开

反转过程：

1
2
3
4
5
6
7
8
9
10
11
12
prev = None 

curr = head 

while curr:     
	nxt = curr.next
	
	curr.next = prev  
	   
	prev = curr    
	 
	curr = nxt

✅ 只要 3 个指针 就够，空间 O(1)。

2. 反转一段子链（已知子链的首尾）

除了 prev/curr/nxt 三个工作指针，还要额外 2 个锚点：

  • sub_prev：子链前驱（前一段的尾）

  • sub_next：子链后继（后一段的头）

反转步骤：

  1. 用 sub_prev 和 sub_next 把子链分离出来

  2. 用 prev/curr/nxt 反转子链

  3. 反转完接回 sub_prev → 新头，新尾 → sub_next

✅ 这里需要 3 个工作指针 + 2 个锚点 = 5 个指针。

3. K 个一组反转

这是你现在问的情况，步骤是：

  1. 用 pre 找到本组前驱

  2. 用 end 找到本组尾巴（走 k 步）

  3. 用 next_group = end.next 保存下一组的起点

  4. 用 prev/curr/nxt 反转 [start, end]

  5. 反转完接回并让 pre 移到新尾（原来的 start）

常用指针：

  • 跨组锚点：pre、end、next_group（3 个）

  • 反转工作：prev、curr、nxt（3 个）

✅ 总共 固定 6 个指针，不随 k 增加而增加。