Why can't I remove occurrences in the linked list?

Question

Problem: Given a value, remove all instances of that value from a linked list. More info below: JAVA

    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode n = head; //1, 2, 6, 3, 4, 5, 6
        while(n.next == null){
            if(n.next.val == val){
                n.next = n.next.next;
            }
            n = n.next;
            if(n == null){break;}
        }
        return head;
    }
}

Since its a pass by reference, it should be updating shouldn't it?

I tried:

removeElements([1,2,6,3,4,5,6], 6)

But it didn't remove anything. So what I am doing incorrectly?

Answer 1

There are a couple of issues:

• you want to loop until a node is null not until is not null (i.e. while( ... != null))
• you might want to loop until n is null, not until n.next is null, otherwise you'd skip the last element
• you want to check for n.val == val not n.next.val == val, otherwise you'd skip the first element
• if you check n you want to keep track of the previous node in case you need to remove n, i.e. prev.next = n.next.
• if the first element (the head) is to be removed you need to replace the head, i.e. return the second element (this can be done by checking prev == null which would mean that n is the current head).

Answer 2

As mentioned by Thomas in his first point, you wrote the while loop incorrectly. Also, because you have a single linked list, you need to keep track of the previous node (also mentioned by Thomas).

public static ListNode removeElements(ListNode head, int val)
{
    ListNode n = head;
    ListNode prev = null; //the previous node.
    while (n != null)
    {
        if (n.value == val)
        {
            //if prev is null it means that we have to delete the head
            //and therefore we need to advance the head
            if (prev == null)
            {
                head = n.next;
                prev = null;//remains at null because there's nothing before head
                n = head;//new head, let's start from here
            } else
            {
                prev.next = n.next; //let's skip the element to delete
                n = n.next;//let's advance to the next node
            }
        } else
        {
            //nothing to delete, let's advance to the next node and make 
            //the current node the previous node in the next iteration
            prev = n;
            n = n.next;
        }

    }
    return head;
}

Answer 3

Its always a good practice to solve these questions with proper test cases. Design the possible test cases including the corner cases. Then follow your algorithm and see if it solves the problem for the test cases. Write the code and dry run it, this will do a sanity check of the code as well as of the logic.

Below are the cases for this question for which test cases must be written.

1. Null list,
2. List with one element and value being equal to the value to be deleted
3. List with one element and value not being equal to the value to be deleted
4. List with two elements and first node value being equal to the value to be deleted
5. List with two elements and last node value being equal to the value to be deleted
6. List with three elements and first node value being equal to the value to be deleted
7. List with three elements and second node value being equal to the value to be deleted
8. List with three elements and last node value being equal to the value to be deleted

Below is the code for the problem of removing nodes with a given value in a linked list.

public ListNode removeElements(ListNode head, int val) {
        while(head != null && head.val == val){
            head = head.next;
        }
        if(head == null){
            return null;
        }
        ListNode node = head;
        while(node.next != null){
            if(node.next.val == val){
                node.next = node.next.next;
            }else{
                node = node.next;
            }
        }
        return head;
}