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?

https://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value — OH GOD SPIDERS, Mar 15 '17 at 15:39
becuase it should be while(n.next != null), also you don't check if the head contains your value. you are missing a lot of check statements for this. — RAZ_Muh_Taz, Mar 15 '17 at 15:41
`while(n.next == null){` will do something very ugly if you pass a list of length 1 to `removeElements` and nothing if the list is longer. — , Mar 15 '17 at 15:42

score 1 · Answer 1 · answered Mar 15 '17 at 15:42

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).

Edd · Answer 2 · 2017-03-15T16:19:33.213

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;
}

score 0 · Answer 3 · answered Mar 15 '17 at 16:39

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.

Null list,
List with one element and value being equal to the value to be deleted
List with one element and value not being equal to the value to be deleted
List with two elements and first node value being equal to the value to be deleted
List with two elements and last node value being equal to the value to be deleted
List with three elements and first node value being equal to the value to be deleted
List with three elements and second node value being equal to the value to be deleted
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;
}

For the first 2 lines `while(head != null && head.val == val){ head = head.next; }` after this loop is done the node is reduced so much isn' it? Say I had `1->2->3->1->null` and the desired `val = 1` then by the time the loop is done `head = null`? — sssszzzzzzssszzz, Mar 15 '17 at 18:58
no as the loop checks if the value at head is equal to desired value and then only modifies head as next node else first loop is stopped. In your case head will be at node with value 2 after 1st loop. — nits.kk, Mar 16 '17 at 02:29

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

3 Answers3