K 个一组翻转链表
题目要求
编写一个函数，实现对链表的分组翻转功能。具体来说，给定一个链表的头节点 head，应该将链表中的每 k 个节点看作一组进行翻转。如果链表中的节点数不是 k 的整数倍，那么最后剩余的节点应保持原有的顺序。在翻转过程中，不能仅仅改变节点的值，而是需要通过改变节点之间的链接关系来实现翻转。
解题思路
解决这个问题可以分为以下几个步骤：
-
遍历链表：首先需要遍历整个链表，确定链表的总长度，以便知道最后一组是否有足够的
k个节点进行翻转。 -
分组翻转：从头节点开始，对链表中的每
k个节点进行翻转。翻转的基本方法是，对于每一组内的节点，逐个将其摘下并插入到当前组的起始位置，直到该组内的节点全部翻转完毕。 -
处理剩余节点：如果链表的长度不是
k的整数倍，那么最后剩余的节点不需要翻转，保持原样即可。 -
链接各组：在翻转每一组节点的同时，需要注意维护好相邻两组之间的链接关系，确保链表的连续性。
-
返回结果：最后返回新链表的头节点，这个头节点是第一次翻转后的头节点。
具体实现时，可以使用几个辅助指针来帮助标记和链接：
prev：指向当前组翻转前的第一个节点的前一个节点，初始时为null。current：当前遍历到的节点。next：指向current节点的下一个节点，用于在翻转节点时不丢失链表的其余部分。tail：当前组翻转前的第一个节点，翻转后将成为该组的尾节点，需要链接到下一组的头节点。
在实现时，需要注意边界条件的处理，如链表长度小于 k，链表为空等情况。
Golang 版本
package main
import (
"fmt"
)
// ListNode is a definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func reverseKGroup(head *ListNode, k int) *ListNode {
if head == nil || k == 1 {
return head
}
// 创建一个虚拟头节点，便于处理头部翻转的情况
dummy := &ListNode{Next: head}
prevGroupEnd := dummy
// 遍历链表，确定链表长度
length := 0
for current := head; current != nil; current = current.Next {
length++
}
// 对每k个节点进行翻转
for length >= k {
current := prevGroupEnd.Next
next := current.Next
for i := 1; i < k; i++ {
current.Next = next.Next
next.Next = prevGroupEnd.Next
prevGroupEnd.Next = next
next = current.Next
}
prevGroupEnd = current
length -= k
}
return dummy.Next
}
func printList(head *ListNode) {
for head != nil {
fmt.Printf("%d ", head.Val)
head = head.Next
}
fmt.Println()
}
func main() {
// 创建一个示例链表 1->2->3->4->5
nodes := []int{1, 2, 3, 4, 5}
dummy := &ListNode{}
current := dummy
for _, val := range nodes {
current.Next = &ListNode{Val: val}
current = current.Next
}
// 应用翻转函数
k := 2
result := reverseKGroup(dummy.Next, k)
// 打印翻转后的链表
printList(result)
}
这段代码定义了一个链表节点 ListNode，实现了一个 reverseKGroup 函数来解决题目中的问题。main 函数创建了一个示例链表，并调用 reverseKGroup 函数进行测试，最后打印出翻转后的链表。
C++版本
#include <iostream>
// Definition for singly-linked list.
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) {
if (head == nullptr || k == 1) {
return head;
}
ListNode dummy(0);
dummy.next = head;
ListNode *prevGroupEnd = &dummy;
while (head != nullptr) {
// Check if there are k nodes left in the list
ListNode *tail = head;
int i;
for (i = 0; i < k; ++i) {
if (tail == nullptr) break;
tail = tail->next;
}
if (i != k) break; // Less than k nodes, no need to reverse
// Reverse k nodes
ListNode *prev = tail, *curr = head, *next = nullptr;
while (curr != tail) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
// Connect with previous part
prevGroupEnd->next = prev;
prevGroupEnd = head;
head = tail;
}
return dummy.next;
}
};
void printList(ListNode* head) {
while (head != nullptr) {
std::cout << head->val << " ";
head = head->next;
}
std::cout << std::endl;
}
int main() {
// Create a sample linked list 1->2->3->4->5
ListNode *list = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
Solution solution;
int k = 2;
ListNode *result = solution.reverseKGroup(list, k);
// Print the reversed list
printList(result);
// Clean up memory
while (result != nullptr) {
ListNode *temp = result;
result = result->next;
delete temp;
}
return 0;
}
这段 C++代码定义了一个链表节点 ListNode 和一个解决问题的类 Solution。Solution 类中的 reverseKGroup 方法实现了题目要求的链表分组翻转功能。main 函数创建了一个示例链表，并调用 reverseKGroup 方法进行测试，最后打印出翻转后的链表，并且在最后进行了内存清理。
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 head is None or k == 1:
return head
# Dummy node initialization
dummy = ListNode(0)
dummy.next = head
prev_group_end = dummy
# Count the number of nodes in the list
count = 0
current = head
while current:
count += 1
current = current.next
# Reverse nodes in k groups
while count >= k:
current = prev_group_end.next
next_node = current.next
for i in range(1, k):
current.next = next_node.next
next_node.next = prev_group_end.next
prev_group_end.next = next_node
next_node = current.next
prev_group_end = current
count -= k
return dummy.next
# Helper function to print the list
def print_list(node):
while node:
print(node.val, end=" ")
node = node.next
print()
# Example usage
if __name__ == "__main__":
# Create a sample linked list 1->2->3->4->5
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i + 1]
head = nodes[0]
# Apply the reverse function
k = 2
solution = Solution()
reversed_list_head = solution.reverseKGroup(head, k)
# Print the reversed list
print_list(reversed_list_head)
这段 Python 代码定义了一个链表节点 ListNode 和一个解决问题的类 Solution。Solution 类中的 reverseKGroup 方法实现了题目要求的链表分组翻转功能。在 if __name__ == "__main__": 部分，代码创建了一个示例链表，并调用 reverseKGroup 方法进行测试，最后打印出翻转后的链表。
Java 版本
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prevGroupEnd = dummy;
ListNode current = head;
// Count the total number of nodes in the list
int count = 0;
while (current != null) {
count++;
current = current.next;
}
// Reverse nodes in k groups
while (count >= k) {
current = prevGroupEnd.next;
ListNode next = current.next;
for (int i = 1; i < k; i++) {
current.next = next.next;
next.next = prevGroupEnd.next;
prevGroupEnd.next = next;
next = current.next;
}
prevGroupEnd = current;
count -= k;
}
return dummy.next;
}
}
public class Main {
public static void printList(ListNode node) {
while (node != null) {
System.out.print(node.val + " ");
node = node.next;
}
System.out.println();
}
public static void main(String[] args) {
// Create a sample linked list 1->2->3->4->5
ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
Solution solution = new Solution();
int k = 2;
ListNode result = solution.reverseKGroup(head, k);
// Print the reversed list
printList(result);
}
}
这段 Java 代码定义了一个链表节点 ListNode 和一个解决问题的类 Solution。Solution 类中的 reverseKGroup 方法实现了题目要求的链表分组翻转功能。Main 类中的 main 方法创建了一个示例链表，并调用 reverseKGroup 方法进行测试，最后打印出翻转后的链表。
Rust 版本
use std::rc::Rc; use std::cell::RefCell; // Definition for singly-linked list. #[derive(PartialEq, Eq, Clone, Debug)] pub struct ListNode { pub val: i32, pub next: Option<Rc<RefCell<ListNode>>>, } impl ListNode { #[inline] fn new(val: i32) -> Self { ListNode { val, next: None, } } } pub struct Solution; impl Solution { pub fn reverse_k_group(head: Option<Rc<RefCell<ListNode>>>, k: i32) -> Option<Rc<RefCell<ListNode>>> { let mut head = head; let mut stack = Vec::new(); let mut current = head.clone(); // Push nodes to stack and pop to reverse in groups of k while let Some(node) = current { stack.push(node.clone()); if stack.len() == k as usize { while let Some(top) = stack.pop() { if stack.is_empty() { // Connect the last node of the reversed group to the next group top.borrow_mut().next = Self::reverse_k_group(top.borrow().next.clone(), k); return Some(top); } // Reverse the link top.borrow_mut().next = stack.last().cloned(); } } current = node.borrow().next.clone(); } // If the number of nodes is not a multiple of k, return the remaining nodes as is head } } fn main() { // Helper function to create a list from a Vec of i32 fn to_list(vec: Vec<i32>) -> Option<Rc<RefCell<ListNode>>> { let mut current = None; for &val in vec.iter().rev() { let mut node = ListNode::new(val); node.next = current; current = Some(Rc::new(RefCell::new(node))); } current } // Helper function to collect values from a list into a Vec<i32> fn collect_values(head: Option<Rc<RefCell<ListNode>>>) -> Vec<i32> { let mut values = Vec::new(); let mut current = head; while let Some(node) = current { values.push(node.borrow().val); current = node.borrow().next.clone(); } values } // Example usage let list = to_list(vec![1, 2, 3, 4, 5]); let k = 2; let reversed_list = Solution::reverse_k_group(list, k); println!("{:?}", collect_values(reversed_list)); }
这段 Rust 代码定义了一个链表节点 ListNode 和一个解决问题的结构体 Solution。Solution 结构体中的 reverse_k_group 函数实现了题目要求的链表分组翻转功能。main 函数中创建了一个示例链表，并调用 reverse_k_group 函数进行测试，最后打印出翻转后的链表的值。
总结
上面给出的解法是针对链表分组翻转问题的不同编程语言版本的实现。无论是使用 Golang、C++、Python、Java 还是 Rust，解决问题的思路都是一致的：
- 首先，需要遍历链表，确定链表的长度，以便后续处理。
- 然后，对链表中的每 k 个节点一组进行翻转。在翻转过程中，需要维护好相邻两组之间的链接关系，确保链表的连续性。
- 如果节点总数不是 k 的整数倍，剩余的节点保持原有顺序。
这些解法都采用了类似的逻辑，但在具体实现上有一些语言特定的差异。例如，不同语言对于链表的表示和操作方式有所不同，因此在代码中会有相应的语言特定的语法和数据结构的使用。