25. K 个一组翻转链表 - 力扣（LeetCode）

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

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

复制代码

示例 2：

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

复制代码

提示：

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

---

思绪如下：
        本题的思绪是基于链表的分组反转操纵。具体来说，就是将链表的节点每 k 个为一组进行反转。首先统计链表的节点个数，如许可以知道是否尚有充足的节点来进行分组反转。创建一个虚拟头节点 dummy ，这个虚拟头节点的 next 指向原链表的头节点，然后初始化三个指针：p0 指向当前处理组的前一个节点（初始为虚拟头节点），pre 用于保存当前节点的前一个节点（初始为 None），cur 用于遍历链表（初始为头节点 head）。
        在分组反转的过程中，每次处理 k 个节点的一组，直到剩余节点数不敷 k 个。在每次处理时，通过一个循环逐个反转节点，保存当前节点的下一个节点到 nxt，将当前节点的 next 指向 pre 实现反转，然后更新 pre 和 cur 指针。
        反转完成后，需要将反转后的子链表毗连到主链表中。这里通过 p0.next 指向反转后的组头节点 pre，而反转前的组头节点（nxt）的 next 指向当前 cur（下一组的第一个节点），末了更新 p0 到下一组的前一个节点。
        这里用表示图俩表示题解实例中完成第一个 k 的反转后的链表，以便参考：

---

题解如下：

1. ​
2. # Definition for singly-linked list.
3. # class ListNode:
4. #     def __init__(self, val=0, next=None):
5. #         self.val = val
6. #         self.next = next
7. class Solution:
8.    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
9.        # 统计链表的节点个数
10.        n = 0
11.        cur = head
12.        
13.        while cur:
14.            n += 1
15.            cur = cur.next
16. ​
17.        # 创建一个虚拟头节点
18.        p0 = dummy = ListNode(next=head)
19.        # pre用于记录当前反转部分的前一个节点，cur用于遍历链表
20.        pre = None
21.        cur = head
22. ​
23.        # 每次处理k个节点的一组
24.        while n >= k:
25.            # 减少剩余需要处理的节点数
26.            n -= k
27.            # 反转当前组的k个节点
28.            for i in range(k):
29.                # 保存当前节点的下一个节点
30.                nxt = cur.next
31.                # 将当前节点的next指向前一个节点pre，实现反转
32.                cur.next = pre
33.                # 更新pre和cur的位置
34.                pre = cur
35.                cur = nxt
36. ​
37.            # 连接反转后的子链表到主链表中
38.            # nxt是p0的下一个节点，即反转前的组头节点
39.            nxt = p0.next
40.            # 将反转后的组尾节点（nxt）的next指向当前cur（下一组的第一个节点）
41.            nxt.next = cur
42.            # 将p0的next指向反转后的组头节点pre
43.            p0.next = pre
44.            # 更新p0到下一组的前一个节点（即当前组的尾节点nxt）
45.            p0 = nxt
46. ​
47.        # 返回虚拟头节点的next，即新的链表头
48.        return dummy.next

复制代码

 

---

题解示例：
  

1. ​
2. 假设链表为 1 -> 2 -> 3 -> 4 -> 5 -> None，k=2。
3. 统计节点个数：n = 5。
4. ​
5. 创建虚拟头节点：dummy.next = 1 -> 2 -> 3 -> 4 -> 5 -> None。
6. 初始化指针：p0 指向 dummy，pre = None，cur = 1。
7. ​
8. 第一次处理 k=2 个节点：
9. 反转 1 -> 2，得到 2 -> 1。
10. 连接反转后的子链表：
11. nxt = 1（p0.next）。
12. 1.next = 3（当前 cur）。
13. p0.next = 2（反转后的组头节点）。
14. 更新 p0 到 1。
15. ​
16. 第二次处理 k=2 个节点：
17. 反转 3 -> 4，得到 4 -> 3。
18. 连接反转后的子链表：
19. nxt = 3（p0.next）。
20. 3.next = 5（当前 cur）。
21. p0.next = 4（反转后的组头节点）。
22. 更新 p0 到 3。
23. ​
24. 剩余节点数不足 k，停止处理。
25. 最终链表为 2 -> 1 -> 4 -> 3 -> 5 -> None。
26. ​

复制代码

---

逻辑梳理：
1. 统计链表节点个数
        首先，遍历链表统计节点总数 n，这有助于判定是否尚有充足的节点进行分组反转。
2. 创建虚拟头节点
        创建一个虚拟头节点 dummy，其 next 指向原链表的头节点。这可以简化界限条件的处理，好比当链表为空或者只有一个节点时的操纵。
3. 初始化指针

• p0：指向当前处理组的前一个节点，初始为虚拟头节点。
  
• pre：用于保存当前节点的前一个节点，初始为 None。
  
• cur：用于遍历链表，初始为头节点 head。
  

4. 分组反转逻辑
每次处理 k 个节点的一组，直到剩余节点数不敷 k 个：

• 减少剩余节点数：n -= k，表示已经处理了一组 k 个节点。
  
• 反转当前组的 k 个节点：
  
  
  
  • 使用一个循环，遍历 k 次，逐个反转节点。
    
  • 在每次循环中：
    
    
    
    • 保存当前节点的下一个节点到 nxt。
      
    • 将当前节点的 next 指向 pre，实现反转。
      
    • 更新 pre 和 cur 指针。
      
    
    
  
  

5. 毗连反转后的子链表

• nxt 是 p0 的下一个节点，即反转前的组头节点。
  
• 将反转后的组尾节点（nxt）的 next 指向当前 cur（下一组的第一个节点）。
  
• 将 p0 的 next 指向反转后的组头节点 pre。
  
• 更新 p0 到下一组的前一个节点（即当前组的尾节点 nxt）。
  

6. 返回效果
        返回虚拟头节点的 next，即新的链表头。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。