Demo: Reverse Linked List

In this assignment, we will solve a more challenging problem with Linked Lists. Without further ado, let's see the problem description:

Problem Description

// Given the head of a linked list, reverse the list and return it.

// Input: 1 -> 2 -> 3 -> 4 -> null
// Output: 4 -> 3 -> 2 -> 1 -> null

Algorithm

Your first instinct might be to do something similar to what we did in the first problem. Initialize two pointers, prev and curr. Set prev to null and curr to head.

In the first step, you could change the next pointer of curr node to point to prev. However, this leads to a problem. Balloons with values 2, 3, and 4 have now flown away like in Lenny Kravitz's song because nothing keeps a reference to them.

Thus, we need to introduce a third variable: nextNode. It will keep a reference to the curr.next node, or, with our analogy, we need the help of another cat. It will hold the next balloon of the curr cat.

---

Let's start over, but let's do it correctly this time.

1. If the head of the linked list is null, return head as there are no nodes in the linked list.
2. Initialize two pointers: prev and curr. Set prev to null, and curr to head.
3. Iterate through the linked list until curr becomes null:
   • Initialize the nextNode variable to reference the curr.next node.
   • Rewire the curr node so that its next pointer points to the prev node. This is our 'reversal' step.
   • Slide the prev and curr pointers. The prev node should now reference curr, and curr should reference nextNode. In previous problems, sliding curr meant using curr = curr.next. Now, we must use our nextNode reference, because we've just altered curr.next to point backwards.
4. Return prev because once curr becomes null, the prev node will reference the new head node.

---

Walkthrough

Here's a step-by-step walkthrough of reversing a linked list 1 -> 2 -> 3 -> 4:

Step 1

We initialize two pointers, prev and curr. Set prev to null and curr to the head of the linked list (1).

Step 2

We initialize a third pointer nextNode to reference curr.next (nextNode = curr.next).

Next, we change the next pointer of curr to reference prev (curr.next = prev).

Then, we slide the prev and curr pointers. The prev node should point to curr, (prev = curr), and curr node should point to nextNode (curr = nextNode).

Step 3

At the beginning of step 3, we set the nextNode variable to point to curr.next which is the node with the value 3 (nextNode = curr.next).

Then, we change the next pointer of curr to point to prev (curr.next = prev).

Finally, we slide prev to reference curr (prev = curr), and curr to reference nextNode (curr = nextNode).

Step 4

Once again, we set nextNode to curr.next (nextNode = curr.next).

Next, we change the next pointer of curr to reference prev (curr.next = prev).

Finally, we assign prev to reference curr (prev = curr), and curr to reference nextNode (curr = nextNode).

Step 5

In the fifth and last step, we set nextNode variable to reference curr.next, which is null.

Next, we change the next pointer of curr to prev (curr.next = prev).

Finally, we slide prev and curr so that prev now references the node with the value 4, and curr is null. Since curr is null, we are done with the iteration, and we can return prev, as it references node 4, which is the new head of the linked list. You might have noticed that the head variable still references the node with the value 1. This is why we can't return head in the end, as that would be the same as returning a list 1 -> null.

The resulting linked list after reversing the original one is now: 4 -> 3 -> 2 -> 1 -> null.

---

Solution Code

Let's take a look at the code implementation of the algorithm:

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function reverseLinkedList(head) {
  if (!head) {
    return head;
  }

  let prev = null;
  let curr = head;

  while (curr !== null) {
    // Hold onto the next node so that we don't lose our list
    let nextNode = curr.next;
    // Reverse the direction of `curr`
    curr.next = prev;
    // Slide pointers
    prev = curr;
    curr = nextNode;
  }
  return prev;
}

// Helper function to print the linked list
function printList(head) {
  let curr = head;
  let result = "";
  while (curr !== null) {
    result += curr.val + " -> ";
    curr = curr.next;
  }
  result += "null";
  return result;
}

// Test case 1
const head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(3);
head1.next.next.next = new ListNode(4);

console.log("Input: ", printList(head1));
console.log("Output:", printList(reverseLinkedList(head1)));
// Input:  1 -> 2 -> 3 -> 4 -> null
// Output: 4 -> 3 -> 2 -> 1 -> null

In this assignment, we have seen that in some problems, we might need to use three pointers (prev, curr, and nextNode) to be able to solve them efficiently.

Another useful tip when trying to solve problems with linked lists is to draw out where your pointers are and what happens in each step when you change next pointers of nodes. This will significantly aid you in solving problems, as you will have a visual representation of the linked list. It will also help you identify any issues, such as the one we encountered in this problem when we rewired curr.next without first assigning it to the nextNode variable. Additionally, visualizing the linked list will provide insights into how to fix such issues.