Coding Problem 6 | Removed Linked List Elements

I struggled with Linked List problems before. I suppose the difficult for me with Linked List is that it is hard to conceptualize the edge cases. They really force you to slow down and check your assumptions about how your program is going to run. One thing I have done with Linked List is actually draw out the Linked List and follow program execution. Here is a problem from leetcode.com which asks you to write a function to remove all nodes with given value from a linked list given the head. The solution seems straight forward but there are edge cases to consider.

Edge case 1 you have a linked list that is null.
[]
In this case you can simply return the head you were given since there are no elements of the list to remove.

if (head==null) {
           return head;
       }

Edge case 2 you have one element and it is the value

[1]

In this case you can point head to the next element to delete the element, even if the next element is null. What if you had multiple elements that were the value we are searching for?

[1]-[1]-[1]

If this occurs then one solution is to turn the check into a loop until you get to a element that is either null or is not the value you are looking for.

[1]-[1]-[1]-[2]

becomes

[2]

and if the element was null we we get an empty list/null head. We can use the code below to take care of this.

while(head != null && head.val == val) {
            head=head.next;
        }

With those two edge cases taken care of we can now safely assume that the head value is not the value we are looking for and is not null. If it is the last element of the list then we can simply return the head. From here we can apply the standard pre/curr pointer idea to remove the matching values from the list. Psuedocode is as follows:

pre = head;
curr = head.next;

while curr != null:
	if curr is value we are looking for
		point pre.next to curr.next to skip curr
		point curr to curr.next to check the next value
	else curr not value we are looking for
		advance pre to pre.next and curr to curr.next
done

return head;

We are basically looking one node ahead of our pre node because we need to know whether to route the previous node in the sequence say n to n+2 (the node containing the value being n+1 for example) thus skipping the value node. This was a problem covered in my undergrad lower divsion data structures class and I have also seen this in an interview. I think just getting familiarity with how to manipulate linked lists will help with this problem…personally I think this problem would be difficult if not prepared for in an interview since I would be willing to wager the vast majority of software devs probably do not deal with LinkedLists regularly. Here is the full code below.

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