Reverse a Linked List From Position m to n

Given the head of a singly linked list and two positions m <= n (counting from 1), reverse the nodes from position m to position n and return the head.

LeetCode: 92. Reverse Linked List II

Example

Text

Input:  15 -> 20 -> 25 -> 30 -> 35, m = 2, n = 4
Output: 15 -> 30 -> 25 -> 20 -> 35

Input:  20 -> 40 -> 60 -> 70, m = 2, n = 3
Output: 20 -> 60 -> 40 -> 70

Brute force: reverse the values

Copy the values into an int[], reverse the range m - 1 to n - 1 in place with two indexes that move toward each other, and build a new list.

A list node here is an object with a mutable next field, and null marks the end of the list.

Java

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

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

    static ListNode reverseBetween(ListNode head, int m, int n) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) values.add(node.val);
        for (int i = m - 1, j = n - 1; i < j; i++, j--) {
            int tmp = values.get(i);
            values.set(i, values.get(j));
            values.set(j, tmp);
        }
        ListNode result = null;
        for (int i = values.size() - 1; i >= 0; i--) {
            result = new ListNode(values.get(i), result);
        }
        return result;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        System.out.println(show(reverseBetween(fromArray(15, 20, 25, 30, 35), 2, 4)));
    }
}

Output

[15, 30, 25, 20, 35]

Time: O(len). Space: O(len), and it rebuilds nodes instead of moving them.

Optimal: relink the segment in one pass

Put a dummy node in front of the head and walk before forward m - 1 steps. before is now the node right before position m. The dummy makes m == 1 work with no special case.
Let start be before.next. It is the first node of the segment and ends up as the last one.
Repeat n - m times: take the node after start (call it moved), cut it out, and insert it right after before.

Text

15 -> [20 -> 25 -> 30] -> 35
       reverse segment
15 -> [30 -> 25 -> 20] -> 35

Walkthrough with 15 -> 20 -> 25 -> 30 -> 35, m = 2, n = 4. Here before is 15 and start is 20.

step	`moved`	list after
1	25	15 -> 25 -> 20 -> 30 -> 35
2	30	15 -> 30 -> 25 -> 20 -> 35

Java

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

    static ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode before = dummy;
        for (int i = 1; i < m; i++) before = before.next;

        ListNode start = before.next;
        for (int i = 0; i < n - m; i++) {
            ListNode moved = start.next;
            start.next = moved.next;   // cut `moved` out of the segment
            moved.next = before.next;  // put it at the front of the segment
            before.next = moved;
        }
        return dummy.next;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        System.out.println(show(reverseBetween(fromArray(15, 20, 25, 30, 35), 2, 4)));
        System.out.println(show(reverseBetween(fromArray(20, 40, 60, 70), 2, 3)));
        System.out.println(show(reverseBetween(fromArray(1, 2, 3), 1, 3)));
        System.out.println(show(reverseBetween(fromArray(1, 2, 3), 2, 2)));
    }
}

Output

[15, 30, 25, 20, 35]
[20, 60, 40, 70]
[3, 2, 1]
[1, 2, 3]

Time: O(n): m - 1 steps to reach before, then n - m relinks. Space: O(1).

start never moves. Each round pulls the node after start to the front of the segment, so start drifts to the end of the segment and its next always points at the first node after the segment. No separate step is needed to attach the rest of the list.

Edge cases

m == n: the loop runs zero times; the list is unchanged.
m == 1: before is the dummy node, so the head itself is replaced and dummy.next is the new head.
n equal to the length: moved.next becomes null at the last step, which correctly ends the list.