Reverse Linked List II Solutions in C++

// Source : https://oj.leetcode.com/problems/reverse-linked-list-ii/
// Author : Hao Chen
// Date   : 2014-07-05



#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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


ListNode *reverseBetween(ListNode *head, int m, int n) {

    if (head==NULL || m>=n) return head;

    ListNode fake(0);
    fake.next = head;
    ListNode *pBegin=&fake, *pEnd=&fake;

    int distance = n - m ;
    while(pEnd && distance>0){
        pEnd = pEnd->next;
        distance--;
    } 
    while(pBegin && pEnd && m-1>0) {
        pBegin = pBegin->next;
        pEnd = pEnd->next;
        m--;
    }
    if (pBegin==NULL || pEnd==NULL || pEnd->next == NULL){
        return head;
    }
    
    ListNode *p = pBegin->next;
    ListNode *q = pEnd->next->next;
    
    ListNode *pHead = q;
    while(p != q){
        ListNode* node = p->next;
        p->next = pHead;
        pHead = p;
        p = node;
    }
    pBegin->next = pHead;

    return fake.next;
    
}



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;
}

ListNode* createList(int len) {
    int *a = new int[len];
    for(int i=0; i<len; i++){
        a[i] = i+1;
    }
    ListNode* h =  createList(a, len);
    delete[] a;
    return h;
}

int main(int argc, char** argv)
{
    int l=5;
    int  m=2, n=4;
    
    if (argc>1){
        l = atoi(argv[1]);
    }
    if (argc>2) {
        m = atoi(argv[2]);
    }
    if (argc>3) {
        n = atoi(argv[3]);
    }
    
    ListNode* h = createList(l);
    printList( h );
    printList( reverseBetween(h , m, n) );

    
}

#include <cstddef>

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

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (!(n-=m)) return head;
        ListNode preHead(0);
        preHead.next = head;
        ListNode *pre = &preHead;
        while (--m) pre = pre->next;
        ListNode *first = pre->next;
        while (n--) {
            ListNode *p = first->next;
            first->next = p->next;
            p->next = pre->next;
            pre->next = p;
        }
        return preHead.next;
    }
};

/// Source : https://leetcode.com/problems/reverse-linked-list-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-10-02

#include <iostream>

using namespace std;


/// Recursive
/// Time Complexity: O(n)
/// Space Complexity: O(n)

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

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {

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

        ListNode* pre = dummyHead;
        for(int i = 0; i < m - 1; i ++, pre = pre->next);

        ListNode* tail = pre->next;
        ListNode* left;
        pre->next = reverse(pre->next, n - m, left);
        tail->next = left;

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

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

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

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


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/reverse-linked-list-ii/description/
/// Author : liuyubobobo
/// Time   : 2019-01-10

#include <iostream>

using namespace std;


/// Non-Recursive
/// Time Complexity: O(n)
/// Space Complexity: O(n)

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

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {

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

        ListNode* pre = dummyHead;
        for(int i = 0; i < m - 1; i ++, pre = pre->next);

        ListNode* tail = pre->next;
        ListNode* left = tail;
        pre->next = reverse(pre->next, n - m, left);
        if(left != tail) tail->next = left;

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

private:
    ListNode* reverse(ListNode* head, int n, ListNode* &left){

        if(!head || !head->next || !n)
            return head;

        ListNode* pre = head, *cur = head->next;
        while(n -- ){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        };
        left = cur;
        return pre;
    }
};


int main() {

    return 0;
}