leetcode-25 Reverse Nodes in k-Group

題意: 其實是上一題(k=2)的延伸版,就是給定一個linked list, 每k個元素要反轉,若不足k個則不用,空間複雜度須為O(1)

解題思路:想法簡單,實現起來不容易,訣竅就是每數到k個元素時反轉,反轉利用三個指標,分別記錄連續三個元素,之後依此類推,須注意邊界條件處理,以免發生null pointer exception

C++ code:

/**
 * 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) {
        
        ListNode* ori=new ListNode(0);
        int count=0;
        if(head==NULL||k==1)
            return head;
        ListNode* e;
        ListNode* o=ori;
        while(head!=NULL)
        {
           
            count++;
            if(count==1)
            {
                e=head;
                o->next=head;
            }
            if(count==k)
            {
                
                o->next=head;
                o=e;
                head=head->next;
                ListNode* temp0=e;
                ListNode* temp=e->next;
                ListNode* temp1=temp->next;
                while(count!=1)
                {
                    temp->next=temp0;
                    temp0=temp;
                    if(count!=1)//avoid access null
                        temp=temp1;
                    if(count!=2)//avoid access null
                        temp1=temp1->next;
                    count--;
                }
                o->next=NULL;
                count--;
                continue;
            }
            head=head->next;
        }
        return ori->next;
    }
};