[LeetCode] Reverse Nodes in K-Group

[Problem]

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

[Analysis]
在 Reverse Linked List II 的基础上做，就非常容易了。

[Solution]

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Definition for Solution
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       
        // the list is not empty
        if(head != NULL){
            ListNode *pre = head;
            ListNode *begin = head;
            ListNode *end = head;
            ListNode *p = head;
   
            // set begin and first
            while(p != NULL && (m > 0 || n > 0)){
                if(m > 0){
                    m--;
                    if(m == 0){
                        begin = p;
                    }
                    else{
                        pre = p;
                    }
                }
                if(n > 0){
                    n--;
                    if(n == 0){
                        end = p;
                    }
                }
                p = p->next;
            }
   
            // because 1 <= m <= n <= length
            // so, the below line can be removed
            //assert(m ==0 && n == 0);
   
            // reverse at head
            bool atHead = false;
            if(pre == begin){
                atHead = true;
            }
   
            // swap begin and end
            ListNode *cur = begin->next;
            if(pre != end){
                pre->next = end;
            }
            begin->next = end->next;
   
            // reverse between begin and end
            pre = begin;
            ListNode *later = cur;
            ListNode *last = end->next;
            while(cur != NULL && cur != last){
                later = cur->next;
                cur->next = pre;
                pre = cur;
   
                // be careful to set the head
                if(atHead){
                    head = cur;
                }
   
                // update cur
                cur = later;
            }
        }
        return head;
    }
   
    // reverse K group
    ListNode *reverseKGroup(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       
        // get length
        int len = 0;
        ListNode *p = head;
        while(p != NULL){
            len++;
            p = p->next;
        }
   
        // reverse
        for(int i = 1; i+k-1 <= len; i += k){
            head = reverseBetween(head, i, i+k-1);
        }
   
        return head;
    }
};

 说明：版权所有，转载请注明出处。 Coder007的博客