这是LeetCode里的第25道题。
题目要求：
给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
示例 :
给定这个链表：
1->2->3->4->5当 k = 2 时，应当返回:
2->1->4->3->5当 k = 3 时，应当返回:
3->2->1->4->5说明 :
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
设计思路：
使用分治法（应该可以这样说吧），不是要k个一组吗？那就把k个节点当做一小块，然后对这一小块进行倒置。然后再连接，难就是难在连接上。如下图（灵魂画师上线了！）：
如图所示，r节点就是连接处，而且此时r节点指向的是NULL，当一组交换完后，p节点指向的也是NULL，而且p节点是这一组的最后一个节点。我们要做的就是把上一组完成的尾巴r节点连接上这一组交换完后的tail节点上。这就是关键之处。当然不能忘了，当到了最后一组不满足等于k时，要记得直接返回。
解题代码：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode* reverse(ListNode *head,ListNode *tail){ 12 if(head==tail)return head; 13 ListNode *p=head,*r=tail; 14 stack<ListNode*>sl; 15 while(p!=r){ 16 sl.push(p); 17 p=p->next; 18 } 19 while(!sl.empty()){ 20 r->next=sl.top(); 21 sl.pop(); 22 r=r->next; 23 } 24 r->next=NULL; 25 return p; 26 } 27 ListNode* reverseKGroup(ListNode* head, int k) { 28 ListNode *phead,*ptail,*res=NULL,*p,*r=NULL; 29 int i=1; 30 phead=ptail=head; 31 while(ptail!=NULL){ 32 if(i==k){ 33 p=ptail->next; 34 if(res==NULL)res=reverse(phead,ptail); 35 else r->next=reverse(phead,ptail); 36 r=phead; 37 phead=ptail=p; 38 i=1;continue; 39 } 40 ptail=ptail->next; 41 i++; 42 } 43 if(i!=1){ 44 if(r==NULL)return head; 45 r->next=phead; 46 } 47 return res; 48 } 49 };
最后结果：
个人总结：
这道题难度是有的，也可以同过递归来缩短代码的长度。也可以在倒置之前先统计出长度，计算出需要倒置的次数，再保存起来。最后连接。
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
