Leetcode 25. Reverse Nodes in k-Group

佚名 6年前 (2019-05-08) 随笔 1279人围观抢沙发百度已收录

https://leetcode.com/problems/reverse-nodes-in-k-group/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        /*
        和24题类似
        因为常数空间，故需要先判断后k个指针是否完整存在
        交换时,第i个与第i+1个指针改成p[i+1]->next=p[i],【i=1,...k-1】
        记录第1个后第k个指针,第k+1个指针
        
        pl->next=prnext
        pre->next=pr
        
        pre=pl
        */
        ListNode* pre=new ListNode(0),*pp=pre,*pl,*pr,*pt,*p1,*p2;
        pre->next=head;
        while(1){
            //判断后面是否有k个,若没有则结束
            pl=pre->next;
            pr=pre;
            for(int i=0;i<k;++i){
                if(pr->next) pr=pr->next;
                else{
                    //没有k个
                    pre=pp->next;
                    delete pp;
                    return pre;
                }
            }
            //有k个的情况
            
            //修改p[l...r]的指针的方向
            p1=pl;
            p2=pl->next;
            while(p1!=pr){
                pt=p2->next;
                p2->next=p1;
                p1=p2;
                p2=pt;
            }
            
            
            //把链表重新相连
            pl->next=p2;//最后p2代表的就是原来pr->next
            pre->next=pr;
            pre=pl;
        }
    }
};