Reverse Linked List II

Reverse Linked List II

 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.

--------------------------------------------- codes ------------------------------------------------------------------
/**
 * 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) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        
        int cnt = 1;
        ListNode *cur = head;
        ListNode *nxt;
        ListNode *newhead = NULL;
        ListNode *pre = NULL;
        ListNode *tail = NULL;
        while (cur) {
            nxt = cur->next;
            if (cnt >= m && cnt <= n) {
                if (cnt == m) {
                    tail = cur;
                }
                cur->next = newhead;
                newhead = cur;
                if (cnt == n) {
                    tail->next = nxt;
                    if (pre) {
                        pre->next = newhead;
                        return head;
                    } else {
                        return newhead;
                    }
                }
            } else {
                //bug here
                //pre should only be updated when cur doesn't reach to m
                pre = cur;
            }
            cnt++;
            cur = nxt;
        }
    }

};
-------------------------- codes -----------------------------------------------------
/**
 * 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 dummy(-1);
        dummy.next = head;
        int count = 1;
        ListNode *pre = &dummy;
        // pay attention to the comparison of count and m 
        while (pre && count < m) {
            count++;
            pre = pre->next;
        }
        ListNode *tail = pre->next;
        ListNode *next = tail->next;
        // pay attention to the comparison of count and m 
        while (count < n) {
            count++;
            ListNode *node = next;
            next = next->next;
            node->next = pre->next;
            pre->next = node;
        }
        tail->next = next;
        return dummy.next;
    }

};