Reverse Linked List II

NeetCode: Reverse Linked List II · LeetCode: 92. Reverse Linked List II · Difficulty: Medium

Given the head of a singly linked list and two 1-indexed positions left <= right, reverse the nodes from position left to position right and return the resulting list.

Example

Text

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, left = 2, right = 4    Output: 1 -> 4 -> 3 -> 2 -> 5
Input:  head = 5,                     left = 1, right = 1    Output: 5

Java linked structures use null and mutable fields, so the list is a chain of ListNode objects, the end is next == null, and the empty list is null. The helper fromArray builds a list from its values and toList copies a list into an ArrayList for printing.

Brute force: copy to an ArrayList, reverse the range, rebuild

Copy the values into a list, reverse the sub-range [left - 1, right) with Collections.reverse on a subList view, and build a fresh list. It allocates a whole new list and does not change any links.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        List<Integer> values = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            values.add(cur.val);
        }
        Collections.reverse(values.subList(left - 1, right)); // end index is exclusive
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

public class Main {
    static ListNode fromArray(int... values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            out.add(cur.val);
        }
        return out;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(toList(s.reverseBetween(fromArray(1, 2, 3, 4, 5), 2, 4)));
        System.out.println(toList(s.reverseBetween(fromArray(5), 1, 1)));
        System.out.println(toList(s.reverseBetween(fromArray(3, 5), 1, 2)));
    }
}

Output

[1, 4, 3, 2, 5]
[5]
[5, 3]

subList returns a view of the list, so reversing the view reverses that range of values.

Time: O(n). Space: O(n).

Optimal: reverse only the window, in place

Put a dummy node in front of the head so that left = 1 needs no special case. Then:

Walk prev to the node just before position left (left - 1 steps from the dummy).
Let cur = prev.next. Repeat right - left times: take the node after cur (move), unlink it from there, and insert it directly after prev.
cur is now the last node of the reversed window and already points at the untouched rest, so nothing else needs re-linking.

For 1 -> 2 -> 3 -> 4 -> 5 with left = 2, right = 4: prev is node 1 and cur is node 2. Moving node 3 to the front of the window gives 1 -> 3 -> 2 -> 4 -> 5. Moving node 4 gives 1 -> 4 -> 3 -> 2 -> 5. Every node is moved; only the dummy is allocated, and the work is at most one pass over right nodes.

Java

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // Move to the node just before position `left`.
        ListNode prev = dummy;
        for (int i = 1; i < left; i++) {
            prev = prev.next;
        }
        // Move the node after `cur` to the front of the window, right - left times.
        ListNode cur = prev.next;
        for (int i = 0; i < right - left; i++) {
            ListNode move = cur.next;
            cur.next = move.next;
            move.next = prev.next;
            prev.next = move;
        }
        return dummy.next;
    }
}

public class Main {
    static ListNode fromArray(int... values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            out.add(cur.val);
        }
        return out;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(toList(s.reverseBetween(fromArray(1, 2, 3, 4, 5), 2, 4)));
        System.out.println(toList(s.reverseBetween(fromArray(5), 1, 1)));
        System.out.println(toList(s.reverseBetween(fromArray(3, 5), 1, 2)));
    }
}

Output

[1, 4, 3, 2, 5]
[5]
[5, 3]

Time: O(n), one pass. Space: O(1) extra.