92. Reverse Linked List II

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

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

ListNode* reverseBetween(ListNode* head, int m, int n) { // time: O(n); space: O(1)
    if (!head) return nullptr;
    ListNode* dummy = new ListNode(-1), *pre = dummy;
    pre->next = head;
    for (int i = 1; i < m; ++i) {
        pre = pre->next;
    }
    ListNode *cur = pre->next, *nex = cur->next;
    for (int j = m; j < n; ++j) {
        cur->next = nex->next;
        nex->next = pre->next;
        pre->next = nex;
        nex = cur->next;
    }
    ListNode* res = dummy->next;
    delete dummy;
    return res;
}

206. Reverse Linked List