25.Reverse Nodes in k-Group (List)

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

思路：注意最后不满k个swap，需要再做一次reverse，使之成为正序。

指针赋值时注意前一个右项作为后一个左向，一一赋值。

/**
 * 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* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* current = head; //the node to do swap
        ListNode* subHead = dummyHead; //the node before the head of the group
        ListNode* subTail; //the last node of the group
        
        while(current && current->next){
            subTail = current;
            current = current->next;
            for(int i = 1; i < k; i++){ //k group needs k-1 swap
                if(current==NULL){
                    //reset: do once more reverse
                    subTail = subHead->next;
                    current = subTail->next;
                    for(int j = 1; j < i; j++){
                        subTail->next = current->next;
                        current->next = subHead->next;
                        subHead->next = current;
                        current = subTail->next;
                    }
                    break;
                }
                
                //assign value one by one
                subTail->next = current->next;
                current->next = subHead->next;
                subHead->next = current;
                current = subTail->next;
            }
            subHead = subTail;
        }
        
        return dummyHead->next;
    }
};

25.Reverse Nodes in k-Group (List)

相关推荐