给定链表和整数k, 使用in-space方法将链表按k个为一组进行倒序, 如果剩余个数不足k个则保留其原始顺序.
?
如给定1->2->3->4->5, k = 2, 需要返回 2->1->4->3->5; 给定1->2->3->4->5, k = 3, 需要返回 3->2->1->4->5.
?
算法描述:
?
使用指针cur遍历链表;
使用指针pilot探索链表, 如果剩余个数不够, 跳出循环, 算法结束; 如果个数足够, 则进行下一步;
只要指针cur和pilot没有相遇, 就依次交换相邻的node;
重新设置cur和pilot, 返回第2步.
需要说明的是第三步交换相邻的node:
?
我们设需要交换的2个node分别为cur和cur->next, 这里用到2个指针: pre指向cur的前一个节点. 变换过程如下
?
?ListNode *nt = cur->next->next;?
?
?nt保存后节点(需要交换的2节点之后的节点)信息.
?
?cur->next->next = pre->next;?
?
?把第2个节点指向第1个节点(新方向).
?
?pre->next = cur->next;?
?
?把前节点(需要交换的2节点之前的节点)指向第2个节点(重新构造开头).
?
?cur->next = nt;?
?
?把第1个节点指向后节点(重新构造结尾).
?
整理后, 两个橘黄色节点已经对调, 并且两者前后节点未变.
?
?
?
?
?
代码:
?
复制代码
?1 class Solution {
?2 public:
?3 ? ? ListNode *reverseKGroup(ListNode *head, int k) {
?4 ? ? ? ? if (head == NULL) return NULL;
?5 ? ? ? ? ListNode *dummy = new ListNode(0);
?6 ? ? ? ? dummy->next = head;
?7 ? ? ? ? ListNode *pre = dummy;
?8 ? ? ? ? ListNode *cur = head;
?9 ? ? ? ? while(cur != NULL) {
10 ? ? ? ? ? ? ListNode *pilot = pre->next;
11 ? ? ? ? ? ? int remaining = k;
12 ? ? ? ? ? ? while (pilot != NULL && remaining-- > 0) pilot = pilot->next;
13 ? ? ? ? ? ? if (remaining > 0) break;
14 ? ? ? ? ? ? while(cur->next != pilot) {
15 ? ? ? ? ? ? ? ? ListNode *nt = cur->next->next;
16 ? ? ? ? ? ? ? ? cur->next->next = pre->next;
17 ? ? ? ? ? ? ? ? pre->next = cur->next;
18 ? ? ? ? ? ? ? ? cur->next = nt;
19 ? ? ? ? ? ? }
20 ? ? ? ? ? ? pre = cur;
21 ? ? ? ? ? ? cur = cur->next;
22 ? ? ? ? }
23 ? ? ? ? return dummy->next;
24 ? ? }
25 };