#P4048. K个一组翻转链表
-
ID: 2290
Tried: 99
Accepted: 30
Difficulty: 6
K个一组翻转链表
题目内容
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换
输入描述
输入包含两行：
第一行包含链表的节点值，用空格隔开。
第二行包含一个整数k。
输出描述
输出链表翻转后的节点值，用空格隔开。
样例1
输入
1 2 3 4 5
2
输出
2 1 4 3 5
样例2
输入
1 2 3 4 5
3
输出
3 2 1 4 5
提示
- 链表中的节点数目为 n
- 1<=k<=n<=5000
- 0<=Node.val<=1000
每k个一组翻转链表
题目分析
本题要求将链表中每连续k个节点作为一组进行翻转，如果剩余节点不足k个，则保持原有顺序。
为实现该功能，我们可以考虑如下方法：
解题思路与算法
本题适合使用链表操作和指针的模拟实现，具体思路为：
- 使用虚拟头节点（dummy node）简化链表的操作。
- 每次从链表头节点开始，判断接下来的k个节点是否存在：
- 如果存在，则进行翻转操作。
- 如果不存在，结束循环，返回结果。
- 翻转每组k个节点时，需要记录前一组的尾节点和下一组的头节点，便于连接已翻转好的部分。
算法流程：
- 创建虚拟头节点，指向链表头。
- 用指针定位需要翻转的一组节点的头尾，执行翻转。
- 完成翻转后重新连接翻转后的链表片段。
- 重复上述步骤直到遍历结束。
复杂度分析
- 时间复杂度：O(n)，其中 n 是链表节点个数，每个节点只会被访问常数次。
- 空间复杂度：O(1)，未使用额外空间。
参考代码
Python代码
# 定义链表节点
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 翻转函数
def reverseKGroup(head, k):
dummy = ListNode(0)
dummy.next = head
prev = dummy
while True:
tail = prev
for i in range(k):
tail = tail.next
if not tail:
return dummy.next
next_group = tail.next
pre, cur = next_group, prev.next
while cur != next_group:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
tmp = prev.next
prev.next = tail
prev = tmp
# 输入处理
vals = list(map(int, input().split()))
k = int(input())
# 构建链表
dummy = ListNode(0)
cur = dummy
for v in vals:
cur.next = ListNode(v)
cur = cur.next
# 执行翻转
res = reverseKGroup(dummy.next, k)
# 输出处理
ans = []
while res:
ans.append(str(res.val))
res = res.next
print(' '.join(ans))
Java代码
import java.util.*;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Main {
public static ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while(true){
ListNode tail = prev;
for(int i=0; i<k; i++){
tail = tail.next;
if(tail == null) return dummy.next;
}
ListNode nextGroup = tail.next;
ListNode pre = nextGroup, cur = prev.next;
while(cur != nextGroup){
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
ListNode tmp = prev.next;
prev.next = tail;
prev = tmp;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String[] vals = sc.nextLine().split(" ");
int k = sc.nextInt();
// 构建链表
ListNode dummy = new ListNode(0), cur = dummy;
for(String val: vals){
cur.next = new ListNode(Integer.parseInt(val));
cur = cur.next;
}
// 执行翻转
ListNode res = reverseKGroup(dummy.next, k);
// 输出结果
List<String> ans = new ArrayList<>();
while(res != null){
ans.add(String.valueOf(res.val));
res = res.next;
}
System.out.println(String.join(" ", ans));
}
}
C++代码
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x): val(x), next(nullptr) {}
};
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev = dummy;
while(true){
ListNode* tail = prev;
for(int i=0; i<k; i++){
tail = tail->next;
if(!tail) return dummy->next;
}
ListNode* nextGroup = tail->next;
ListNode* pre = nextGroup, *cur = prev->next;
while(cur != nextGroup){
ListNode* tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
ListNode* tmp = prev->next;
prev->next = tail;
prev = tmp;
}
}
int main(){
string line;
getline(cin, line);
stringstream ss(line);
vector<int> vals;
int num;
while(ss >> num) vals.push_back(num);
int k;
cin >> k;
// 构建链表
ListNode dummy(0), *cur = &dummy;
for(int v : vals){
cur->next = new ListNode(v);
cur = cur->next;
}
// 执行翻转
ListNode* res = reverseKGroup(dummy.next, k);
// 输出结果
vector<int> ans;
while(res){
ans.push_back(res->val);
res = res->next;
}
for(int i = 0; i < ans.size(); i++){
if(i) cout << " ";
cout << ans[i];
}
cout << endl;
return 0;
}