Thursday, October 10, 2013

Reverse Nodes in k-Group [Leetcode]

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

Solution: before do k-group reversion, we first need to check if the current linked list has at least one k-group. If not, we simply do nothing, otherwise we reverse it to get a new k-group, say k'. Then we recursively reverse the rest of nodes, and append the resulting linked list to the end of k'.

/**
 * 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) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(k<=0) return head;
        ListNode* cur = head;
        //check if the linked list has at least k nodes
        int c = 0;
        while(cur!=NULL && c<k){
            cur=cur->next;
            ++c;
        }
        //the linked list has less than k nodes
        if(c<k)
            return head;
        //the linked list has at least k nodes
        ListNode* nxtHead = cur;
        //reverse the first k-group
        ListNode* pre = NULL;
        cur = head;
        c=0;
        while(c<k){
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
            ++c;
        }
        //do k-group reversion to the rest of nodes, and then append it to the reversed first k-group
        head->next = reverseKGroup(nxtHead, k);
        return pre;
    }
};

No comments:

Post a Comment