# Programming Interview Questions 5: Linked List Remove Nodes

This is a very fundamental question and it’s tricky to implement without any bugs. Given a linkedlist of integers and an integer value, delete every node of the linkedlist containing that value.

There are many corner cases to consider, here are some. The value to remove is 5.

Inputs are the head of the linked list and the integer value to remove. The most important corner case occurs when the element to delete is at the head of the linkedlist. So the caller’s head pointer should be updated. Because of this, our function should take the head either as a pointer to pointer or pass by reference (or we can also return the new head pointer back to the caller). Otherwise the changes won’t be seen by the caller. I personally prefer pass by reference since it leads to cleaner code.

Let’s say we want to remove all the nodes with the value 5. The solution is first we remove all consecutive fives in the beginning of the linkedlist, and update the head accordingly to point to the first element other than 5 (can be null as well). Then we begin a loop and check the next node whether its value is 5. If it isn’t then we advance the pointer to the next node and continue. If it is 5 then we modify the next pointers accordingly and delete the next note. But we don’t advance our pointer, this is very important. Because the new next node could also contain the value 5, and if we advance the pointer we won’t be able to delete it. This is a subtle corner case which occurs when two or more consecutive nodes should be deleted. Here is the C code:

```typedef struct Node{ int val; Node *next; } Node;   void removeNodes(Node* &head, int rmv) { while (head!=NULL && head->val==rmv) { Node *temp=head; head=head->next; free(temp); } if (head==NULL) return;   Node *current=head; while (current->next!=NULL) { if (current->next->val==rmv) { Node *temp=current->next; current->next=temp->next; free(temp); } else { current=current->next; } } }```

The time complexity is O(N) and space complexity is O(1), which is optimal. I especially like this interview question because it demonstrates fundamental concepts and it’s not easy to code bug free.

VN:F [1.9.11_1134]
Programming Interview Questions 5: Linked List Remove Nodes, 8.3 out of 10 based on 4 ratings

This entry was posted in Programming Interview. Bookmark the permalink.

### 4 Responses to Programming Interview Questions 5: Linked List Remove Nodes

1. Anonymous says:

you can also merge it in one loop:

list *p = head, *prev = 0, *t;
while(p != 0) {
if(p->val != a) {
prev = p;
p = p->next;
continue;
}
t = p->next;
if(prev != 0) {
prev->next = t;
} else {
}
delete p;
p = t;
}
}

• Arden says:

Yes but the number of comparisons is more important than the number of loops. At every iteration you check whether the head should be modified or not by prev!=0. This comparison would be true most of the time, because the number of times the removed node will appear in the beginning of the linkedlist is very low compared to the other locations. So most of the time you won’t need to modify the head. And if the linkedlist is long you will keep making this comparison, even after you performed all consecutive removals in the beginning of the linkedlist. So, given a linkedlist of length 1 million which doesn’t contain any 5s, you will make this extra comparison a million times even though it’s not necessary. That’s why I seperated those cases in two different loops, to avoid the extra unnecessary comparisons.

2. Anonymous says:

The following pattern removes the need for special cases.

``` Node* RemoveNodesWithValue(Node* head, int k) { if (!head) { return head; }```

``` Node dummy; dummy.next = head; Node* prev = &dummy; Node* current = head; while (current) { if (current->data == k) { prev->next = current->next; delete current; current = prev->next; } else { prev = current; current = current->next; } } ```

``` return dummy.next; } ```

• Arden says:

Great solution, thanks!