Demo: Remove Twos

In this assignment, we will learn how to solve problems using Linked Lists. While you may find the problems challenging at first, they will become easier to solve with time and practice.

To tackle problems with Linked Lists, we will employ pointer-based strategies that we have learned in previous lessons. Typically, the problems will involve singly linked lists, where we do not have access to a reference of the previous node. As a result, we will frequently use two pointers: prev, which points to the previous node, and curr, which points to the current node. Sometimes, we may also require a reference to the next node, which we will store in a variable called next.

Let's explore how we can work with these pointers using an example.

Problem Description

// Given the head of a linked list, remove all
// occurrences of the value 2 from the linked list.

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

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

// Input:  null
// Output: null

Algorithm

To solve this problem, we will use the following algorithm:

1. Initialize two pointers: prev and curr. Set prev to null and curr to the head of the linked list.

2. Begin iterating, checking the value of curr on each iteration.

   • If curr is null:
     • Break from our loop. There are no more elements to remove. If this happens on the first iteration, we've been given an empty linked list.
   • If curr has a value of 2 (our target value):
     • Check if prev is null. If so, update the head of the linked list to curr.next.
     • If prev is not null, set prev.next to curr.next to bypass curr and remove it from the list.
   • If curr has a value that is not 2:
     • Update the prev pointer to curr.
   • Move the curr pointer to the next node.

3. Return the updated linked list.

---

Walkthrough

Here's a step-by-step walkthrough of removing occurrences of the value 2 from the linked list 1 -> 2 -> 3 -> 2 -> 4:

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

Step 2: We begin iterating through the linked list until curr becomes null. In this step, since curr is not equal to the value 2, which is our target value, we slide pointers.

Step 3: In the third step, the value of the curr node is 2, so we reassign the next pointer of the prev node to the curr.next, and by doing so, we remove the node with the value 2 from the linked list. Afterward, we simply slide the curr pointer.

Step 4: In the fourth step, the value of the curr node isn't 2, so we just slide pointers.

Step 5: In this step, the value of the curr node is 2, so we first reassign the next pointer of prev node to curr.next, and afterwards, we slide curr pointer.

Step 6: In the final step, the value of the curr node is not the target. We slide both pointers and since curr is now null, we return the head node which represents our linked list.

The resulting linked list after removing all occurrences of the target value 2 is 1 -> 3 -> 4.

---

Solution Code

Now, 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 deleteTwos(head) {
  let prev = null;
  let curr = head;

  if (!head) {
    return head;
  }

  while (curr) {
    if (curr.val === 2) {
      if (!prev) {
        head = curr.next;
      } else {
        prev.next = curr.next;
      }
    } else {
      prev = curr;
    }
    curr = curr.next;
  }

  return head;
}

// Helper function to format the linked list into a string
function stringifyList(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(2);
head1.next.next.next.next = new ListNode(4);

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

// Test case 2
const head2 = new ListNode(2);
head2.next = new ListNode(3);
head2.next.next = new ListNode(2);

console.log("Input: ", stringifyList(head2));
console.log("Output:", stringifyList(deleteTwos(head2)));
// Input:  2 -> 3 -> 2 -> null
// Output: 3 -> null

In the next assignment, we will use an analogy to help you gain a better understanding of how to work with pointers in Linked Lists.