题目描述
一个链表，每 k 个节点一组进行翻转，返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，最后剩余的节点保持原有顺序。
示例 : 给定链表：1->2->3->4->5，当 k = 2 时，应当返回: 2->1->4->3->5；当 k = 3 时，应当返回: 3->2->1->4->5
说明 : 只能使用常数的额外空间。不能只是单纯的改变节点内部的值，需要实际的进行节点交换。
解决方案
双向队列会比较适合这次的题目，按序压入，再反序取出连起来。为了编程方便，加了preHeader.
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
| struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head || !head->next || k <= 1)
return head;
ListNode* preh;
preh = new ListNode(-1);
preh->next = head;
ListNode* lenp=head;
int i;
bool flag = true;
do {
deque<ListNode*> d;
for (i=1; lenp && i < k; i++){
d.push_front(lenp);
lenp = lenp->next;
}
if (!lenp && i<=k)
if (!d.empty())
preh->next = d.back();
return head;
d.push_front(lenp);
ListNode* n1 = d.back();
n1->next = lenp->next;
ListNode* n2 = d.front();
preh->next = n2;
if (flag){
head = n2;
flag = false;
}
for (int j = 1; j < k; j++){
d.pop_front();
n2->next = d.front();
n2 = n2->next;
}
lenp = d.front()->next;
preh= d.front();
d.pop_front();
} while (true);
}
|
倒是挺有意思的一道题。本来以为会是在两两交换的基础上完成这道题目，现在发现使用了合适的数据结构，真是能节省不少精力。或许两两交换那道题目也可以做一些改进。
在上面的代码中或许加一个后驱会方便一些。
用递归的方法也可以解这个题，每次交换待反转结点的第一个和最后一个。
真 面向样例编程 唉 什么时候才能真正有质变啊