25. K 个一组翻转链表 - 力扣(LeetCode)

基础知识要求：

Java：方法、while循环、for循环、if else语句

Python： 方法、while循环、for循环、if else语句

题目： 

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

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

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

示例 1：

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

示例 2：

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

提示：

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

思路解析：

1. 准备阶段：
   • 首先，我们需要一个哑节点（dummy node）来简化头节点的处理。哑节点是一个不存储实际数据的节点，它的next指针指向链表的头节点。这样，我们就可以避免处理头节点翻转时的特殊情况。
   • 初始化三个指针：prev（前一个子链表的末尾节点）、curr（当前子链表的开始节点）和end（当前子链表的末尾节点）。开始时，prev指向哑节点，curr指向头节点。
2. 循环处理阶段：
   • 在每次循环中，我们首先使用getKthNode函数找到当前子链表的末尾节点end。如果end是null，说明剩下的节点数不足k个，我们不需要再翻转，直接结束循环。
   • 如果end不是null，说明当前子链表至少有k个节点，可以进行翻转。在翻转之前，我们需要保存下一个子链表的开始节点，即end.next，因为翻转后我们会丢失对它的引用。
   • 使用reverse函数翻转当前子链表。翻转后，curr（原来的开始节点）会变为翻转后的末尾节点，并且它的next指针会指向下一个子链表的开始节点。
   • 更新prev和curr的位置。prev指向curr（翻转后的末尾节点），curr指向下一个子链表的开始节点（即之前保存的end.next）。
3. 结束阶段：
   • 当循环结束后，我们得到了一个每k个节点一组翻转后的链表。这个链表的头节点是哑节点的next指针所指向的节点。
   • 返回哑节点的next指针作为结果。

Java代码示例：

public class ListNode {  int val;  ListNode next;  ListNode(int x) { val = x; }  
}  public class Solution {  public ListNode reverseKGroup(ListNode head, int k) {  if (head == null || k <= 1) {  return head;  }  // 创建一个哑节点(dummy node)，简化头节点处理  ListNode dummy = new ListNode(0);  dummy.next = head;  ListNode prev = dummy; // 前一个子链表的末尾节点  ListNode curr = head; // 当前子链表的开始节点  while (curr != null) {  // 计算当前子链表的末尾节点  ListNode end = getKthNode(curr, k);  if (end == null) {  // 不足k个节点，无需翻转，直接退出循环  break;  }  // 翻转当前子链表  ListNode nextGroup = end.next; // 下一个子链表的开始节点  end.next = null; // 切断当前子链表与后续链表的连接  prev.next = reverse(curr); // 翻转后的子链表连接到前一个子链表的末尾  curr.next = nextGroup; // 翻转后的子链表的末尾节点指向下一个子链表的开始节点  // 更新指针  prev = curr; // 前一个子链表的末尾节点移动到当前翻转后的子链表的末尾  curr = nextGroup; // 当前子链表的开始节点移动到下一个子链表的开始节点  }  return dummy.next; // 返回修改后的链表头节点  }  // 翻转链表  private ListNode reverse(ListNode head) {  ListNode prev = null;  ListNode curr = head;  while (curr != null) {  ListNode next = curr.next;  curr.next = prev;  prev = curr;  curr = next;  }  return prev; // 返回翻转后的头节点  }  // 获取第k个节点  private ListNode getKthNode(ListNode head, int k) {  ListNode curr = head;  for (int i = 0; i < k && curr != null; i++) {  curr = curr.next;  }  return curr;  }  
}

Python代码示例：

class ListNode:  def __init__(self, val=0, next=None):  self.val = val  self.next = next  class Solution:  def reverseKGroup(self, head: ListNode, k: int) -> ListNode:  if not head or k <= 1:  return head  # 创建一个哑节点(dummy node)，简化头节点处理  dummy = ListNode(0)  dummy.next = head  prev = dummy  # 前一个子链表的末尾节点  curr = head   # 当前子链表的开始节点  while curr:  # 计算当前子链表的末尾节点  end = self.getKthNode(curr, k)  if not end:  # 不足k个节点，无需翻转，直接退出循环  break  # 翻转当前子链表  next_group = end.next  # 下一个子链表的开始节点  end.next = None  # 切断当前子链表与后续链表的连接  prev.next = self.reverse(curr)  # 翻转后的子链表连接到前一个子链表的末尾  curr.next = next_group  # 翻转后的子链表的末尾节点指向下一个子链表的开始节点  # 更新指针  prev = curr  # 前一个子链表的末尾节点移动到当前翻转后的子链表的末尾  curr = next_group  # 当前子链表的开始节点移动到下一个子链表的开始节点  return dummy.next  # 返回修改后的链表头节点  # 翻转链表  def reverse(self, head: ListNode) -> ListNode:  prev = None  curr = head  while curr:  next_node = curr.next  curr.next = prev  prev = curr  curr = next_node  return prev  # 返回翻转后的头节点  # 获取第k个节点  def getKthNode(self, head: ListNode, k: int) -> ListNode:  curr = head  for _ in range(k):  if curr:  curr = curr.next  else:  return None  return curr