【LeetCode】Reverse Nodes in k-Group(k个一组翻转链表)

来源：cnblogs　　作者：1000sakura　　时间：2018/12/3 10:13:34　　对本文有异议

这是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时，要记得直接返回。

解题代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode *head,ListNode *tail){
        if(head==tail)return head;
        ListNode *p=head,*r=tail;
        stack<ListNode*>sl;
        while(p!=r){
            sl.push(p);
            p=p->next;
        }
        while(!sl.empty()){
            r->next=sl.top();
            sl.pop();
            r=r->next;
        }
        r->next=NULL;
        return p;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *phead,*ptail,*res=NULL,*p,*r=NULL;
        int i=1;
        phead=ptail=head;
        while(ptail!=NULL){
            if(i==k){
                p=ptail->next;
                if(res==NULL)res=reverse(phead,ptail);
                else r->next=reverse(phead,ptail);
                r=phead;
                phead=ptail=p;
                i=1;continue;
            }
            ptail=ptail->next;
            i++;
        }
        if(i!=1){
            if(r==NULL)return head;
            r->next=phead;
        }
        return res;
    }
};