Open Bookshelf Cover Page
Preface
Getting Started
- Prerequisites
- Introduction
The PEDAC Approach to Problem Solving
Introduction to Data Structures and Algorithms
Sorting Algorithms
Pointer-Based Mental Models
Binary Search
Linked Lists
Stacks & Queues
Conclusion
- Conclusion & Next Steps
Share on

Practice: Remove Every Second

In this assignment, we'll practice the techniques learned so far in this lesson with the "Remove Every Second" problem.

Problem Description

// In this problem, you need to implement a function
// `removeEverySecondNode` that accepts a singly linked list
// as an argument. The function should remove every alternate
// node, starting with the second node.

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

function printLinkedList(head) {
  let currentNode = head;
  let listStr = '';
  while (currentNode !== null) {
    listStr += currentNode.val + ' -> ';
    currentNode = currentNode.next;
  }
  listStr += 'null';
  console.log(listStr);
}

function createLinkedList(arr) {
  let head = new ListNode(0);
  let current = head;
  arr.forEach(val => {
    current.next = new ListNode(val);
    current = current.next;
  });
  return head.next;
}

let list1 = createLinkedList([1, 2, 3, 4, 5]);
let list2 = createLinkedList([1, 2]);
let list3 = createLinkedList([1]);
let list4 = createLinkedList([1, 2, 3, 4]);
let list5 = createLinkedList([]);

printLinkedList(removeEverySecondNode(list1)); // Expected: 1 -> 3 -> 5 -> null
printLinkedList(removeEverySecondNode(list2)); // Expected: 1 -> null
printLinkedList(removeEverySecondNode(list3)); // Expected: 1 -> null
printLinkedList(removeEverySecondNode(list4)); // Expected: 1 -> 3 -> null
printLinkedList(removeEverySecondNode(list5)); // Expected: null

Walkthrough & Solution

To solve this problem, we'll use a curr pointer that will start at head.

We will traverse the linked list and adjust the next pointer of a given node so that it skips over the immediate next node. We can accomplish this via curr.next = curr.next.next. This operation effectively removes the node referenced by curr.next from the linked list by bypassing it.

After performing this removal, we'll move curr forward to continue the process from the newly adjusted position in the list (curr = curr.next). This step is crucial as it maintains the continuity of the traversal, essentially moving the point of operation one step ahead in the list.

The process concludes when we encounter a scenario where curr or curr.next is null, indicating we have reached the end of the list or there are no more nodes to skip. Finally, we can return the head node, which is the starting point of the modified list.

Let's see this visually:

We are given a linked list 1 -> 2 -> 3 -> 4 -> 5, and our goal is to remove every second node, resulting in the list 1 -> 3 -> 5.

Initializing the Necessary Variables

For this problem, we only need to introduce one additional variable, curr, which will keep track of the current node in the list. We will initialize curr to the head node. It's important to note that we cannot use the head node for tracking purposes because if we were to move its reference, we would lose the reference to the head node (the node with the value 1 in this case).

STEP 1

We are starting with both head and curr pointing at the node 1.

Since we want to skip the second node, we need to adjust the link so that curr.next points tocurr.next.next.

After we do this, we only need to slide the curr pointer (curr = curr.next). curr.next previously referenced the node with value 2, but now that we've deleted this node, curr.next references the node with value 3.

STEP 2

Our work for the second iteration is much the same. curr references the node with value 3.

We want to skip the second node, so we need to adjust the link so that curr.next points tocurr.next.next.

After we do this, we slide the curr pointer (curr = curr.next).

STEP 3

We have reached the condition where curr.next is pointing to null.

Therefore, we exit the loop and return the head node which is our result list 1 -> 3 -> 5 -> null.

function removeEverySecondNode(head) {
  let curr = head;
  while (curr && curr.next) {
    curr.next = curr.next.next;
    curr = curr.next;
  }
  return head;
}