Reverse Nodes in k-Group Solutions in C++

// Source : https://oj.leetcode.com/problems/reverse-nodes-in-k-group/
// Author : Hao Chen
// Date   : 2014-07-05



#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode *reverseList(ListNode *&head, int k);

ListNode *reverseKGroup(ListNode *head, int k) {

    if (k<=0) return head;
    ListNode fake(0);
    fake.next = head;
    ListNode* p = &fake;

    while(p){
        p->next = reverseList(p->next, k);
        for(int i=0; p && i<k; i++){
            p = p->next;
        }
    }

    return fake.next;
}

ListNode *reverseList(ListNode *&head, int k){
    ListNode* pEnd=head;
    while (pEnd && k>0){
        pEnd = pEnd->next;
        k--;
    }
    if (k>0) return head;

    ListNode *pHead=pEnd, *p=head;
    while(p != pEnd){
        ListNode *q = p->next;
        p->next = pHead;
        pHead = p;
        p = q;
    }
    return pHead;
}

void printList(ListNode* h)
{
    while(h!=NULL){
        printf("%d ", h->val);
        h = h->next;
    }
    printf("\n");
}

ListNode* createList(int a[], int n)
{
    ListNode *head=NULL, *p=NULL;
    for(int i=0; i<n; i++){
        if (head == NULL){
            head = p = new ListNode(a[i]);
        }else{
            p->next = new ListNode(a[i]);
            p = p->next;
        }
    }
    return head;
}


int main(int argc, char** argv)
{
    int a[] = {1,2,3,4,5,6,7,8,9,10};
    ListNode* pList = createList(a, sizeof(a)/sizeof(int));

    int k =2;
    if (argc>1){
        k = atoi(argv[1]);
    }

    pList = reverseKGroup(pList, k);
    printList(pList);
    
    return 0;
}

#include <cstddef>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if (!head || !head->next || k<2) return head;
        ListNode pre(0);
        pre.next = head;

        for (ListNode *front = &pre, *back = &pre; true; front = head, back = head) {
            for (int count = k; count > 0; --count)
                if (!(back = back->next)) return pre.next;

            for (head = front->next; front->next != back; ) {
                ListNode *next = front->next;
                front->next = next->next;
                next->next = back->next;
                back->next = next;
            }
        }
        return pre.next;
    }
};

/// Source : https://leetcode.com/problems/reverse-nodes-in-k-group/description/
/// Author : liuyubobobo
/// Time   : 2019-08-09

#include <iostream>
#include <vector>

using namespace std;


/// Linear Scan and Recursive Reverse
/// Time Complexity: O(n)
/// Space Complexity: O(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) {

        ListNode* dummyHead = new ListNode(-1);
        dummyHead->next = head;

        ListNode* pre = dummyHead;
        while(pre && pre->next){

            ListNode* end = pre;
            int i;
            for(i = 0; i < k && end->next; i ++)
                end = end->next;

            if(i != k) break;

            ListNode* next = end->next;

            // reverse from pre->next to end
            ListNode* rhead = reverse(pre->next, end);

            ListNode* tail = pre->next;
            pre->next = rhead;
            tail->next = next;
            pre = tail;
        }

        ListNode* ret = dummyHead->next;
        delete dummyHead;
        return ret;
    }

private:
    ListNode* reverse(ListNode* head, ListNode* end){

        if(head == end) return head;

        ListNode* rhead = reverse(head->next, end);
        head->next->next = head;
        return rhead;
    }
};


/// LinkedList 测试辅助函数

// 根据n个元素的数组arr创建一个链表, 并返回链表的头
ListNode* createLinkedList(const vector<int>& arr){

    if(arr.size() == 0)
        return NULL;

    ListNode* head = new ListNode(arr[0]);
    ListNode* curNode = head;
    for(int i = 1 ; i < arr.size() ; i ++){
        curNode->next = new ListNode(arr[i]);
        curNode = curNode->next;
    }

    return head;
}

// 打印以head为头结点的链表信息内容
void printLinkedList(ListNode* head){

    ListNode* curNode = head;
    while(curNode != NULL){
        cout << curNode->val << " -> ";
        curNode = curNode->next;
    }

    cout << "NULL" << endl;

    return;
}

// 释放以head为头结点的链表空间
void deleteLinkedList(ListNode* head){

    ListNode* curNode = head;
    while(curNode != NULL){
        ListNode* delNode = curNode;
        curNode = curNode->next;
        delete delNode;
    }

    return;
}


int main() {

    vector<int> arr1 = {1, 2, 3, 4, 5};
    ListNode* res1 = Solution().reverseKGroup(createLinkedList(arr1), 3);
    printLinkedList(res1);
    deleteLinkedList(res1);

    return 0;
}

/// Source : https://leetcode.com/problems/reverse-nodes-in-k-group/description/
/// Author : liuyubobobo
/// Time   : 2018-10-02

#include <iostream>
#include <vector>

using namespace std;


/// Linear Scan and Recursive Reverse
/// Time Complexity: O(n)
/// Space Complexity: O(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) {

        ListNode* dummyHead = new ListNode(-1);
        dummyHead->next = head;

        ListNode* cur = dummyHead;
        while(cur && cur->next){
            ListNode* tail = cur->next;

            ListNode* left;
            bool ok = false;
            cur->next = reverse(cur->next, k - 1, left, ok);
            tail->next = left;

            if(ok)
                cur = tail;
            else {
                tail = cur->next;
                cur->next = reverse(cur->next, k - 1, left, ok);
                tail->next = NULL;
                break;
            }
        }

        ListNode* ret = dummyHead->next;
        delete dummyHead;
        return ret;
    }

private:
    ListNode* reverse(ListNode* head, int index, ListNode* &left, bool& ok){

        if(index == 0 || !head->next){
            ok = index == 0;
            left = head->next;
            return head;
        }

        ListNode* tail = head->next;
        ListNode* ret = reverse(head->next, index - 1, left, ok);
        tail->next = head;
        return ret;
    }
};


/// LinkedList 测试辅助函数

// 根据n个元素的数组arr创建一个链表, 并返回链表的头
ListNode* createLinkedList(const vector<int>& arr){

    if(arr.size() == 0)
        return NULL;

    ListNode* head = new ListNode(arr[0]);
    ListNode* curNode = head;
    for(int i = 1 ; i < arr.size() ; i ++){
        curNode->next = new ListNode(arr[i]);
        curNode = curNode->next;
    }

    return head;
}

// 打印以head为头结点的链表信息内容
void printLinkedList(ListNode* head){

    ListNode* curNode = head;
    while(curNode != NULL){
        cout << curNode->val << " -> ";
        curNode = curNode->next;
    }

    cout << "NULL" << endl;

    return;
}

// 释放以head为头结点的链表空间
void deleteLinkedList(ListNode* head){

    ListNode* curNode = head;
    while(curNode != NULL){
        ListNode* delNode = curNode;
        curNode = curNode->next;
        delete delNode;
    }

    return;
}


int main() {

    vector<int> arr1 = {1, 2, 3, 4, 5};
    ListNode* res1 = Solution().reverseKGroup(createLinkedList(arr1), 3);
    printLinkedList(res1);
    deleteLinkedList(res1);

    return 0;
}