Leetcode 25. Reverse Nodes in k-Group

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

• Version 1

/**
 * 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) {
        return reverse(head, k);
    }
    
    ListNode* reverse(ListNode* node, int k) {
        int count = 0;
        vector<ListNode*> nodes;
        ListNode* current = node;
        while(current) {
            count++;
            nodes.push_back(current);
            if(count == k) {
                break;
            }
            current = current->next;
        }
        if(count < k) {
            return node;
        }
        nodes[0]->next = reverse(nodes[nodes.size() - 1]->next, k);
        for(int i = nodes.size() - 1; i > 0; i--) {
            nodes[i]->next = nodes[i - 1];
        }
        return nodes[nodes.size() - 1];
    }
};

• Version 2

/**
 * 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) {
        return reverse(head, k);
    }
    
    ListNode* reverse(ListNode* node, int k) {
        int count = 0;
        ListNode* current = node;
        while(current && count < k) {
            count++;
            current = current->next;
        }
        if(count < k) {
            return node;
        }
        ListNode* latter = node->next;
        node->next = reverse(current, k);
        ListNode* pre = node;
        current = node->next;
        while(count > 1) {
            ListNode* next = latter->next;
            latter->next = pre;
            pre = latter;
            latter = next;
            count--;
        }
        return pre;
    }
};

Reference

1. https://leetcode.com/problems/reverse-nodes-in-k-group/description/