Reverse Nodes in k-Group

Description

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.

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

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /**
     * @param head a ListNode
     * @param k an integer
     * @return a ListNode
     */
    ListNode *reverseKGroup(ListNode *head, int k) {
        // Write your code here
        if (!head) { 
            return nullptr;
        }
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;
        while (prev->next) {
            prev = in_reKgroup(prev, k);
        }
        return dummy.next;
        // divide the List into Kgroup
        // for every group, reverse and then connect rest
    }
    ListNode* in_reKgroup(ListNode* prev, int k) {
        // find pos 
        ListNode* cur = prev;
        ListNode* goupStart = prev->next;
        while (cur->next && k > 0) {
            --k;
            cur = cur->next;
        }
        // if the group length < k, we did noting
        if (k > 0) {
            return cur;
        }
        // if the group length >= k, we did reverse
        ListNode* rest = cur->next;
        cur->next = nullptr;
        ListNode* newhead = reverse_wtrest(prev->next, rest);
        prev->next = newhead;
        // return the last node of current kgroup after reversing
        return goupStart;
    }
    ListNode* reverse_wtrest(ListNode* head, ListNode* rest) {
        ListNode* tail = rest;
        while (head) {
            ListNode* tmp = head->next;
            head->next = tail;
            tail = head;
            head = tmp;
        }
        return tail;
    }
};

Similar problems

x

Tags

x