Linked List: Reverse Between

Topic

Implement a member function called reverseBetween(m, n) that reverses the nodes between indexes (using 0-based indexing) m and n (inclusive) in the linked list.

Note: this linked list class does not have a tail which will make this method easier to implement.

Output:

• The function should reverse the nodes between the indexes m and n in the linked list. The reversal should be done in-place.

Constraints:

• You are not allowed to use any additional data structures (such as arrays) or modify the existing data structure.
• You can only traverse the linked list once.

Example 1:

Suppose you have a LinkedList object, list, with the following values:
1 -> 2 -> 3 -> 4 -> 5

After calling the reverseBetween(1, 3) function:

list.reverseBetween(1, 3);

The linked list should now have the following values:
1 -> 4 -> 3 -> 2 -> 5

Example 2:

Now suppose you have a LinkedList object, list, with the following values:
1 -> 2 -> 3 -> 4 -> 5 -> 6

After calling the reverseBetween(3, 5) function:

list.reverseBetween(3, 5);

The linked list should now have the following values:
1 -> 2 -> 3 -> 6 -> 5 -> 4

Pseudo Code:

1. If the head of the list is null, return

2. Create a dummy node with value 0

3. Set the next of the dummy node to the head of the list

4. Initialize prev pointer to the dummy node

5. Loop from 0 to m-1

• Move prev pointer one step ahead in the list

6. Initialize current pointer to the next node of prev pointer

7. Loop from 0 to n-m

• Set temp pointer to the next node of current pointer
• Update the next of current pointer to the next of temp pointer
• Update the next of temp pointer to the next of prev pointer
• Update the next of prev pointer to the temp pointer

8. Set the head of the list to the next of the dummy node

Explained another way:

Let’s break it down step by step using simpler terms. We are looking at a LinkedList class, and a method named reverseBetween(m, n).

You can think of a linked list as a chain of boxes (or "nodes"), where each box has a number and a pointer to the next box. The pointer is just the address of the next box.

Let's take a look at the reverseBetween(m, n) function.

1. First, it checks if the linked list (chain of boxes) is empty (head is null). If it is, there’s nothing to do, so it just returns.
2. Then, it creates a dummy node. This node doesn’t contain any meaningful data for our list, but it’s a helpful tool used to simplify the logic of the function.
3. We have a variable prev that starts from the dummy node, and then moves m steps along the chain. This will be the node before the section we want to reverse.
4. current is the next node after prev, which is the first node in the section that we want to reverse.
5. We then enter a loop, which runs n - m times. In each round of the loop, we take the next node after current (let's call it temp), and rearrange the pointers to make it the first node in the reversed section, pushing current and all previously moved nodes one step back. We do this by:

• updating current.next to skip the temp node,
• updating temp.next to point at the start of the reversed section (prev.next), and
• updating prev.next to make temp the first node in the reversed section.

6. After the loop finishes, all the nodes between m and n have been reversed.

7. Finally, we need to update the head of our list to be the node after our dummy node, since the dummy node was just a helper and doesn't actually belong to our list.

Solution Explaination

reverseBetween(m, n) {
        if (this.head === null) return;
 
        const dummy = new Node(0);
        dummy.next = this.head;
        let prev = dummy;
 
        for (let i = 0; i < m; i++) {
            prev = prev.next;
        }
 
        let current = prev.next;
        for (let i = 0; i < n - m; i++) {
            const temp = current.next;
            current.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }
 
        this.head = dummy.next;
    }

The reverseBetween(m, n) function is used to reverse a portion of a linked list between positions m and n, inclusive.

Here's a step-by-step explanation of the logic:

1. If the head of the linked list is null, return, as there is nothing to reverse.
2. Create a dummy node and set its next pointer to the head of the linked list. This dummy node simplifies the manipulation of pointers, especially at the beginning of the list.
3. Initialize a prev pointer and set it to the dummy node. Move the prev pointer m steps forward using a for loop. After the loop, prev will point to the node right before the mth node.
4. Initialize a current pointer to the mth node by setting it to prev.next.
5. Iterate through the list n — m times using a for loop, reversing the portion of the list between positions m and n: a. Create a temp pointer and set it to the next node of current. b. Update the next pointer of current to point to the node after temp. c. Update the next pointer of temp to point to the node right after prev. d. Update the next pointer of prev to point to temp.
6. After the loop, the portion of the linked list between positions m and n has been reversed. Set the head of the linked list to the next pointer of the dummy node.

The function traverses the list only once, making it efficient with a time complexity of O(n), where n is the number of nodes in the list.

Full Code

class Node {
    constructor(value){
        this.value = value;
        this.next = null;
    }
}
 
class LinkedList {
    constructor(value) {
        const newNode = new Node(value);
        this.head = newNode;
        this.length = 1;
    }

    printList() {
        let temp = this.head;
        while (temp !== null) {
            console.log(temp.value);
            temp = temp.next;
        }
    }

    getHead() {
        if (this.head === null) {
            console.log("Head: null");
        } else {
            console.log("Head: " + this.head.value);
        }
    }

    getLength() {
        console.log("Length: " + this.length);
    }

    makeEmpty() {
        this.head = null;
        this.length = 0;
    }
 
 push(value) {
  const newNode = new Node(value);
  if (!this.head) {
   this.head = newNode;
  } else {
   let current = this.head;
   while (current.next !== null) {
    current = current.next;
   }
   current.next = newNode;
  }
  this.length++;
 }
 
 reverseBetween(m, n) {
        if (m === n) {
            return this.head;
        }
        let current = this.head;
        let previous = null;
        let count = 1;
        while (current !== null && count <= m) {
            previous = current;
            current = current.next;
            count++;
        }
        let lastNodeOfFirstPart = previous;
        let lastNodeOfSubList = current;
        let next = null;
        count = 0;
        while (current !== null && count < n - m + 1) {
            next = current.next;
            current.next = previous;
            previous = current;
            current = next;
            count++;
        }
        if (lastNodeOfFirstPart !== null) {
            lastNodeOfFirstPart.next = previous;
        } else {
            this.head = previous;
        }
        lastNodeOfSubList.next = current;
    }


}



let myLinkedList = new LinkedList(1);
myLinkedList.push(2);
myLinkedList.push(3);
myLinkedList.push(4);
myLinkedList.push(5);

console.log("Original list:");
myLinkedList.printList();

const m = 2;
const n = 4;
myLinkedList.reverseBetween(m, n);

console.log(`\nList after reversing between indexes of ${m} and ${n}:`);
myLinkedList.printList();

/*
    EXPECTED OUTPUT:
    ----------------
    Original list:
    1
    2
    3
    4
    5
    List after reversing between indexes of 2 and 4:
    1
    2
    5
    4
    3
*/