Friday, April 26, 2013

Leetcode: Reverse Linked List II in C++



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->NULLm = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given mn satisfy the following condition:
1 <= m <= n <=length of list.

Solution: Learn from discuss in Leetcode. Great Method.
 ListNode *reverseBetween(ListNode *head, int m, int n) {
    ListNode dummy(0);
    dummy.next = head;

    ListNode *start, *pre = &dummy;
    for (int i = 1; i <= n; ++i) {
        if (i == m) start = pre;
        if (i > m && i <= n) {
            pre->next = head->next;
            head->next = start->next;
            start->next = head;
            head = pre;
        }
        pre = head;
        head = head->next;
    }
    return dummy.next;
    }

No comments:

Post a Comment