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

Solution

Approach 1: Iterative Link Reversal.

Approach 2: Recursion.

Code (Python)

Approach 1:

    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        # iterative
        if m >= n or not head or not head.next or m == 0 or n == 0:
            return head
        dummy = ListNode(0)
        dummy.next = head
        prev, first = dummy, head
        for _ in range(m - 1):
            prev, first = prev.next, first.next
        second = first.next
        for _ in range(n - m):
            third = second.next
            second.next = first
            first = second
            second = third
        prev.next.next = second
        prev.next = first
        return dummy.next

Approach 2:

Code (C++)

Approach 1:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
// Iterative Link Reversal.
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode dummyHead(0);
        dummyHead.next = head;
        ListNode *prev = &dummyHead;
        ListNode *curr = head;
        for (int i = 1; i < m; ++i)
        {
            prev = curr;
            curr = curr->next;
        }
        ListNode *next = curr->next;
        for (int i = m; i < n; ++i)
        {
            ListNode *nextNext = next->next;
            next->next = curr;
            curr = next;
            next = nextNext;
        }
        prev->next->next = next;
        prev->next = curr;
        return dummyHead.next;
    }
};

Approach 2:

// Recursion.
class Solution {
private:
    ListNode *left;
    bool stop;
    void doReverseBetween(ListNode *right, int m, int n) {
        if (n == 1)
            return;
        // Place the left & right pointers to the proper places.
        right = right->next;
        if (m > 1)
            left = left->next;
        doReverseBetween(right, m - 1, n - 1);
        // Reverse.
        if (left == right || right->next == left)
            stop = true;
        if (!stop)
            std::swap(left->val, right->val);
        if (left)
            left = left->next;
    }
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        left = head;
        stop = false;
        doReverseBetween(head, m, n);
        return head;
    }
};