Leetcode: Reverse Linked List II

Readme.md

Leetcode: Reverse Linked List II

http://oj.leetcode.com/problems/reverse-linked-list-ii/

Problem Description

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Structures

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

solution-iterative-1.cpp

/*
 * To do this elegantly in one pass is a challenge. The trick is to have a dummy
 * pointer (called newHead in the code below) that points to the head. This will
 * then allow edge cases to be handled effortlessly.
 *
 * In this solution, I change each element
 * I don't think this solution is as elegant as the next iterative solution,
 * but I must admit it uses less pointers
 */

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (!head || m==n) return head;
        
        ListNode newHead(0),
                 *start = NULL,
                 *tail = head;
        
        newHead.next = head;
        start = &newHead;
        
        for (int i=0; i < n; i++) {
            if (i >= m) {
                tail->next = head->next;
                head->next = start->next;
                start->next = head;
                head = tail;
            }
            
            if (i < m-1) {
                start = start->next;
            }
            
            tail = head;
            head = head->next;
        }
        
        return newHead.next;
    }
};

solution-iterative-2.cpp

/*
 * I think this more elegant than the 1st iterative solution,
 * but maybe it because I did it more recently
 */

class Solution {
public:
    ListNode *reverseBetween(ListNode *current, int m, int n) {
        ListNode dummy(INT_MIN), *prev=NULL, *tail=NULL;
        dummy.next = current;
        current = &dummy;
        
        for (int i=0; i <= n; i++) {
            ListNode *next = current->next;
            if (i == m) tail = current;
            if (i >= m && i <= n) current->next = prev;
            prev = current;
            current = next;
        }
        
        tail->next->next = prev;
        tail->next = current;
        
        return dummy.next;
    }
};

solution-recursive.cpp

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, ListNode *&newHead, ListNode *& tail, int m, int n, int c) {
        if (c==n) {
            newHead = head;
            tail = head->next;
            return head;
        }
        
        ListNode *node = reverseBetween(head->next, newHead, tail, m, n, c+1);
        
        if (c >= m) {
            node->next = head;
        } else if (c == m-1) {
            head->next->next = tail;
            head->next = newHead;
        }
        
        return head;
    }

    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode dummyNode(INT_MIN);
        ListNode *newHead = NULL, *tail = NULL;
        dummyNode.next = head;
        
        reverseBetween(&dummyNode, newHead, tail, m, n, 0);
        
        return dummyNode.next;
    }
};