In a lot of problems, we are asked to reverse the links between a set of nodes of a LinkedList. Often, the constraint is that we need to do this in-place, i.e., using the existing node objects and without using extra memory.

In-place Reversal of a LinkedList pattern describes an efficient way to solve the above problem.

Base case

Keep track of previous pointer.

public ListNode reverse(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode prev = null, curr = head;
    while (curr != null) {
        var next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Extended case

Reverse between (and again keep track of prev and do not forget to rearrange pointers).

public ListNode reverse(ListNode head, int n, int m) {
    if (head == null || head.next == null) return head;
    ListNode curr = head, prev = null;
    for (int i = m; i > 1; i--) {
        prev = curr;
        curr = curr.next;
    }
    var preStart = prev;
    var start = curr;
    ListNode next;
    int k = n - m;
    while (curr != null && k >= 0) {
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
        k--;
    }
    start.next = curr;
    if (preStart != null)
        preStart.next = prev;
    else
        head = prev;

    return head;
}

Untitled

Complexities.

In this type of problem we're looking for O(n) time and O(1) space complexity.