题目简介：
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明：
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
思路：
首先设置一个翻转链表的函数，能将翻转后的头和尾传递出来。为了保存起始的头结点，设置一个结点指向起始的头结点。
将链表分为 k 个一组，head指向每组的头结点，若该分组长度大于等于 k ，则翻转该部分链表。在翻转时，还需要当前head的前一个结点pre，从而可以使翻转后的子链表的头部再接回pre，并需要每次子链表尾部的下一个结点nextnode，使翻转后的子链表的尾部接回nextnode。
代码如下：
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
55
56
57
58
59
60
61
62
63
64
|
class Solution {
public:
pair<ListNode*, ListNode*> ReverseLink(ListNode* head, ListNode* tail){
ListNode* pre = tail -> next;
ListNode* now = head;
while(pre != tail){
ListNode* nextnode = now -> next;
now -> next = pre;
pre = now;
now = nextnode;
}
return {tail, head};
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* hair = new ListNode(0);
hair -> next = head;
ListNode* pre = hair;
while(head){
ListNode* tail = pre;
for(int i = 0; i < k; i++){
tail = tail -> next;
if(!tail)
return hair -> next;
}
ListNode* nextnode = tail -> next;
pair<ListNode*, ListNode*> res = ReverseLink(head, tail);
head = res.first;
tail = res.second;
pre -> next = head;
tail -> next = nextnode;
head = tail -> next;
pre = tail;
}
return hair -> next;
}
};
|
