The question

Given a linked list of integers and an integer value, delete every node of the linked list containing that value.

The solution

The tricky part about this problem is taking care of the edge cases. You have to go through all the elements in the list, so the efficiency is O(n).

  • Initialize one variable(lastGood) to null
  • Initialize one variable(first) to the head
  • Check the first element on the linked list(current)
    • If it is not the number you are looking for assign lastGood=current and move current to the next node
    • If it is the number then check if lastGood has a value assigned
      • if lastGood doesn’t have a value it means we want to remove the first item so assign first to current.next
      • if lastGood has a value then assign lastGood.next to current.next
  • Repeat for all elements

Here is the source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// This works like a linked list
// 3 -> 3 -> 5 -> 3
head = {
  value: 3,
  next: {
    value: 3,
    next: {
      value: 5,
      next: {
        value: 3,
        next: null
      }
    }
  }
};

function removeNodes(listHead, remove) {
  var first = listHead;
  var current = listHead;
  var lastGood = null;
  while (current) {
    if (current.value === remove) {
      if (lastGood) {
        lastGood.next = current.next;
      } else {
        first = current.next;
      }
    } else {
      lastGood = current;
    }

    current = current.next;
  }

  return first;
}

function test() {
  var result = removeNodes(head, 3);

  if (result.value === 5 && result.next === null) {
    console.log('success');
  } else {
    console.log('failure');
  }
}

test(); // Prints success
[ application_design  computer_science  algorithms  javascript  programming  ]
Sorting algorithms computer_science algorithms javascript programming
Raft for reaching consensus computer_science algorithms
The Rabin-Karp algorithm computer_science algorithms javascript programming
Load testing a Rails app with Vegeta application_design programming
House painting problem computer_science algorithms javascript programming