Reverse a sublist of linked list

Learn how to create an algorithm to reverse sublist of linked list.

Given a linked list and two range m and n we have to reverse all the elements between this range.

Example

Input:
1 -> 2 -> 3 -> 4 -> 5 -> null
m = 2, n = 4

Output:
1 -> 4 -> 3 -> 2 -> 5 -> null

Note here the index starts from 1 unlike in array where it starts from 0 and we have to perform this in one go.

Reverse sublist of linked list in a given range.

Conceptually this is how our algorithm will work

• Iterate till the last range.
• Store the previous elements from where the reverse index starts.
• Reverse the elements in the given range.
• Mark the remaining elements as the next of reversed sublist.
• Then add this reversed sublist to the previous elements.

We can break the above examples as

1. Prev elements: 1 -> next.
2. Reversed sublist: 4 -> 3 -> 2 -> next.
3. Remaining list: 5 -> null.

At the end merge them 1 -> 4 -> 3 -> 2 -> 5 -> null. Its done.

const reverseBetween = (head, m, n) => {
    //If same then return the head
    if (m === n) {
        return head;
    }

    let index = 1;
    //To track list
    let current = head;
    //To reverse elements
    let previous = null,
        next = null;
    //To track elements before reversing
    let reverse_prev = null;

    //Iterate till we have to reverse
    while (current && index <= n) {
        //If element is in the range
        //Reverse them
        if (index >= m && index <= n) {
            previous = current;
            current = current.next;
            previous.next = next;
            next = previous;
        } else {
        //Store the elements before reverseing starts
           reverse_prev = current;
            current = current.next;
        }

        index++;
    }

    //If there are previous elements
    //Then mark the reversed elements as its next
    if (reverse_prev) {
        reverse_prev.next = next;
    } else {
        //Else whole list is reversed so return it
        reverse_prev = head = next;
    }

    //If there are still elements left after reverse range
    //Add them after the reversed sublist
    if (current) {
        while (reverse_prev.next) {
           reverse_prev = reverse_prev.next;
        }
        reverse_prev.next = current;
    }

    //Return the head
    return head;
};

Input:
const ll1 = new linkedlist();

ll1.append(1);
ll1.append(2);
ll1.append(3);
ll1.append(4);
ll1.append(5);

let s = reverseBetween(ll1.getHead(), 2, 3);

while (s) {
    console.log(s.element);
    s = s.next;
}

Output:
1
3
2
4
5

Time compleixty: O(max(n, (n - m)));
Space compleixty: O(1).