Reverse Linked List II

LeetCode #92

Description:

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

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

Example:

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

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

Idea:

pre and curr这两个指针不变，left是在m,n这一段左边的node，right是这一段右边的node。

Code:

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m==n) return head;
        ListNode dummy_head(-1);
        dummy_head.next = head;

        ListNode *pre, *curr, *left=&dummy_head, *right;

        ListNode *element=head;

        for(int i=1; i<=n; ++i){
            if(i==m-1) left=element;

            element=element->next;
        }

        right=element;

        pre=right;

        curr=left->next;

        while(curr != right){
            ListNode *tmp = curr->next;
            curr->next=pre;
            pre=curr;
            curr=tmp;
        }

        left->next=pre;
        return dummy_head.next;



    }
};