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.

Reverse Linked List II.cpp

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int ttt = m;
        ListNode tmpHead(-1);
        tmpHead.next = head;
        
        ListNode* mHead = &tmpHead;
        
        while(--m) {
            mHead = mHead->next;
        }
        
        ListNode* nNode = &tmpHead;
        ++n;
        while(n--) {
            nNode = nNode->next;
        }
        
        ListNode* mNode = mHead->next;
                
        ListNode bHead(-1);
        bHead.next = nNode;
        while(mNode != nNode) {
            ListNode* tmp = mNode->next;
            mNode->next = bHead.next;
            bHead.next = mNode;
            mNode = tmp;
        }
        
        mHead->next = bHead.next;
        
        
        if(ttt == 1) {
            return bHead.next;
        } else {
            return head;
        }
        
        
        
        
    }
};

Reverse Linked List II.java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // create a pre head pointing to head
        ListNode preHead = new ListNode(-1);
        preHead.next = head;
        ListNode runner = preHead;
        // go to the pointer just before mth node
        for(int i = 1; i < m; ++i) {
            runner = runner.next;
        }
        // save the nodes after nth in backup.next
        ListNode tail = preHead;
        // this needs go beyond the nth element, that's why i starts with 0
        for(int i = 0; i < n; ++i) {
            tail = tail.next;
        }
        ListNode backup = new ListNode(-1);
        backup.next = tail.next;
        tail.next = null;
        // reverse the part
        runner.next = reverseList(runner.next);
        // append the tail (backup)
        ListNode current = preHead.next;
        while(current.next != null) {
            current = current.next;
        }
        current.next = backup.next;
        return preHead.next;
    }
    
    private ListNode reverseList(ListNode head) {
        // -1 -> null
        ListNode preHead = new ListNode(-1);
        // current(1) -> 2 -> 3 -> 4 -> 5 -> null
        ListNode current = head;
        while(current != null) {
            ListNode tmp = current.next;
            current.next = preHead.next;
            preHead.next = current;
            current = tmp;
        }
        return preHead.next;
    }
}