LeetCode-92: Reverse Linked List II

Info

LeetCode-92: Reverse Linked List II

Question

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

img

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Follow up: Could you do it in one pass?

Thoughts

• We just need to partially reverse the LinkedList.
• Left & Right position are recorded by Int value.
• If we can record head and tail and just reverse the part which needs to be reversed.
• How to reverse a linkedlist?

Solution

Reverse sequentially

Take an example of list below:

$$Origin:9\to 7\to 2\to 5\to 4\to 3\to 6$$$$AfterReverse:9\to 7\to 3\to 4\to 5\to 2\to 6$$

Core:

• Find the head node and tail node position in the node part which we want to do reverse.
• Find the node before head (oFront node 7) and after tail(oTail node 6), cause we need to use it to refracture a linkedlist.
• Reverse the inner linkedlist sequentially, with head becoming the tail and tail becoming the head.
• Refacture the whole linkedlist with inner list(Link the inner list with oFront node and oTail node).

Extreme Cases

Notice that in some cases, the oFront/oTail might be null.

For example, left = 1 || right = 7, so we might handle these cases extra.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode cur = head;
        ListNode prev = null;
        ListNode front = null;
        ListNode tail = null;
        ListNode oFront = null;

        int count = 0;
        ListNode next;
        if (left == right) {
            return head;
        }
        while (count <= right) {   
            count++;
            if (count <= left) {
                // record head and oFront
                if (count == left) {
                    front = cur;
                    oFront = prev;
                }
                // Normal Forward
                prev = cur;
                cur = cur.next;
            } else {
                // reverse sequentially
                next = cur.next;
                cur.next = prev;
                prev = cur;
                cur = next;
                if (count == right) {
                    tail = prev; 
                    // Check oFront exist? (if left != 1)
                    if (oFront != null) {
                        oFront.next = tail;
                    }
                    front.next = cur;
                    // handle extreme cases
                    if (cur == null && oFront == null) {
                        return tail;
                    } else if (cur == null) {
                        return head;
                    } else if (oFront == null) {
                        return tail;
                    } else {
                        break;
                    }
                }
            }
        }
        return head;
    }
}

Complexity Analysis

Time-Complexity: $O(N)$

Zone-Complexity: $O(1)$

Reverse by head insertion (Copy)

©️ Copied

📝 Praticed ✅

Core: Same as reverse sequentially, only difference is reverse by head insertion.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode preHead = new ListNode(-1);
        preHead.next = head;
        ListNode prev = preHead;
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }
        ListNode cur = prev.next;
        for (int i = 0; i < right - left; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }
        return preHead.next;
    }
}

Complexity Analysis

Time-Complexity: $O(N)$

Zone-Complexity: $O(1)$

Reflection

Reverse the LinkedList

Talking to reverse linkedlist, there are always two ways to do the reverse.

1. Reverse sequently.
2. Reverse by head insertion.

But keep this in mind, both ways need three parts to do that.

Prev Cur Next

What we really need to do, is to make the order of Assignment Process clear.