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.22_1171]
Rating: 8.0/10 (20 votes cast)
Programming Interview Questions 5: Linked List Remove Nodes, 8.0 out of 10 based on 20 ratings

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

    you can also merge it in one loop:

    list *linked_list_delete(int a, list *head) {
    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 {
    head = t;
    }
    delete p;
    p = t;
    }
    return head;
    }

    • Arden

      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.

  • Anonymous

    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

      Great solution, thanks!

  • Sachin

    void RemoveNodesWithValue(Node** head, int k) {
    Node* toDelete;
    while((*head) != NULL) {
    if ((*head)->data == k) {
    toDelete = (*head);
    *head = (*head)-> next;
    delete toDelete;
    continue;
    }
    head = &((*head)->next);
    }

  • Sachin


    1 void RemoveNodesWithValue(Node** head, int k) {
    2 Node* toDelete;
    3 while((*head) != NULL) {
    4 if ((*head)->data == k) {
    5 toDelete = (*head);
    6 *head = (*head)-> next;
    7 delete toDelete;
    8 continue;
    9 }
    10 head = &((*head)->next);
    11 }

  • sathvik

    Using recursion: the call would be head = Delete(head,key)

    private Node Delete(Node current, int key)
    {
    if (current == null) return null;

    if (current.key == key)
    {
    current = current.next;
    current = Delete(current, key);
    }
    else current.next = Delete(current.next, key);

    return current;
    }

  • http://chanduthedev.blogspot.com Chandu

    Good explanation. Explained with different cases for deleting.

  • http://www.facebook.com/harkirat.saluja Harkirat Saluja

    #include

    struct node
    {
    int a;
    struct node *link;
    };

    void add(struct node **p,int n)
    {
    struct node *temp,*r;
    temp=*p;
    if(*p==NULL)
    {
    temp=malloc(sizeof(struct node));
    temp->a=n;
    temp->link=NULL;
    *p=temp;

    }
    else
    { temp=*p;
    while(temp->link!=NULL)
    {
    temp=temp->link;
    }
    r=malloc(sizeof(struct node));
    r->a=n;
    temp->link=r;
    r->link=NULL;

    }
    }

    void display(struct node *a)
    {
    while(a!=NULL)
    {
    printf(“%d”,a->a);
    a=a->link;
    }
    }

    void delete(struct node **a,int n)
    {
    struct node *temp,*temp1;
    temp=*a;
    temp1=temp->link;
    if(temp->a==n)
    {
    temp->link=NULL;
    *a=temp1;
    }
    else
    {
    while(temp->link!=NULL)
    {
    if((temp->link->a)==n)
    {
    temp->link=temp->link->link;

    }
    temp=temp->link;
    temp1=temp1->link;

    }

    }

    }
    void main()
    {
    struct node *p;
    p=NULL;

    add(&p,5);
    add(&p,6);
    add(&p,7);
    add(&p,8);
    display(p);
    delete(&p,7);
    printf(“n”);
    display(p);
    }

    when i am trying this all working fine but last node is not getting deleted… any help

    • rahul

      while(curr->link!=NULL)

      {

      if((next->a)==n)

      {

      printf(“Inside cond”);

      curr->link=next->link;

      break;

      } else {

      curr=curr->link;

      next=next->link;

      printf(“curr->a %d n”, curr->a);

      printf(“next->a %d n”, next->a);

      }

      }

  • Guest

    Here is the C# code

    public ListNode removeNodeWithCertainValue(ListNode firstNode, int value)

    {

    if (firstNode == null)

    {

    return null;

    }

    if (firstNode.NextListNode == null)

    {

    if(firstNode.NodeValue == value){

    return null;

    }

    return firstNode;

    }

    //there may be multiple nodes with the given value

    while (firstNode!= null && firstNode.NodeValue == value)

    {

    firstNode = firstNode.NextListNode;

    }

    //this check is needed in case all nodes have the provided value

    if (firstNode != null)

    {

    firstNode.NextListNode = removeNodeWithCertainValue(firstNode.NextListNode, value);

    }

    return firstNode;

    }

    • Fatih

      To note, this is the recursive version. I have removed my name accidentally :)

  • Swati Sharma

    Check out these youtube videos on link list and data structure: (http://www.youtube.com/watch?v=92S4zgXN17o&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P), Very well explained!

  • Nikhil

    I don’t understand why we need two while loops. Is the following not a correct implementation?

    //DeleteAll
    // head is part of your Linked List Class
    void deleteAll(int data)
    {
    Node * temp = NULL;
    Node * curr = head;
    while(curr != NULL)
    {
    if(curr->data == data)
    {
    temp = curr->next;
    free(curr);
    head = curr = temp;
    }
    else
    curr = curr->next;
    }
    }

    • Vishal Hemnani

      This code will keep updating head pointer even when the value to be found is not in head pointer.
      Include a condition if(curr->data == data && curr == head) (not sure of the C syntax).

  • Aditya Shrivastava

    Java implementation: private static ListNode Remove(ListNode node, int value)

    public class ListNode {
    int value;
    ListNode node;
    private ListNode(int value)
    {
    this.value=value;
    }
    private ListNode()
    {
    }
    private ListNode Add(int value)
    {
    ListNode node = new ListNode(value);
    this.node=node;
    return node;
    }
    public static void main(String[] args)
    {
    ListNode node=new ListNode(1);
    node.Add(2).Add(5).Add(5).Add(3);
    System.out.println(“start”);
    Print(node);
    node=Remove(node,5);
    System.out.println();
    Print(node);
    System.out.println();
    System.out.println(“done”);
    }
    private static ListNode Remove(ListNode node, int value)
    {
    if(node == null)
    return null;
    if(node.value == value)
    return Remove(node.node,value);
    node.node=Remove(node.node,value);
    return node;
    }
    private static void Print(ListNode node)
    {
    if(node != null)
    {
    System.out.print(node.value + ” “);
    Print(node.node);
    }
    }
    }