Deleting all the matching items in single linked list

Question

I have the following code which I implemented to delete all the nodes for the matching value. My code handles all the 63 varieties of test case scenarios including scenarios like deleting 1 from linked list 1->1, leaving the linked list empty.

 public ListNode RemoveElements(ListNode head, int val) {
 if(head != null)
 {
 ListNode current = head;
 ListNode prevNode;
 while(current !=null && current.next != null)
 {
 prevNode = current;
 if(current.val == val)
 {
 current.val = current.next.val;
 current.next = current.next.next;
 }
 else
 current = current.next;
 }
 int count = 0;
 ListNode p = head;
 ListNode pBefore = null;
 while(p != null)
 {
 if(p.next != null)
 pBefore = p;
 p = p.next;
 count++;
 }
 if(current.val == val)
 {
 if(count == 1)
 head = null;
 else if(count > 1)
 pBefore.next = null;
 }
 }
 return head; 
}

I'm sure this can be optimized and it would be great if someone can share the best way to delete all the matching items in single linked list.

I tried searching on Google, but everywhere it is handled as part of a SingleLinked list custom class having head and tail node access. In my case, I am handling in a method and I have access only to the head of the list through the input parameter.

• SuperBiasedMan: Welcome to Code Review! One clarifying question. You said you want to optimise the script, did you mean with performance or optimised some other way?

Answer 1

Several issues jump in the eyes:

• very complicated logic
• very strange "removal" logic: copy value from next node + delete next node
• is recommended to use braces even on single statement if-else
• messy indentation

This can be done a lot simpler, by using a dummy node:

ListNode dummy = new ListNode();
dummy.next = head;
ListNode runner = dummy;
while (runner.next != null)
{
 if (runner.next.val == val)
 {
 runner.next = runner.next.next;
 }
 else
 {
 runner = runner.next;
 }
}
return dummy.next;

Answer 2

ListNode

Though ListNode isn't a bad name - it could be better. Consider SinglyLinkedListNode (LinkedListNode already exists in the BCL)

Properties should be PascalCased and not use abbreviations, next should be Next and val should be Value.

public class SinglyLinkedListNode
{
 public SinglyLinkedListNode Next { get; set; }
 public int Value { get; set; }
}

This is a good candidate for a generic class too:

public class SinglyLinkedListNode<T>
{ 
 public SinglyLinkedListNode<T> Next { get; set; }
 public T Value { get; set; }
}

Then you aren't limited to just integers.

RemoveElements

I'd say it's a good name

You should return early to save some indentation:

public ListNode RemoveElements(ListNode head, int val)
{
 if(head == null)
 {
 return null;
 }
 // omitted

You aren't using prevNode you should remove it.

I was part way through writing a better solution but Janos beat me to it!

Answer 3

Your code mixes two approaches for deleting a node from a single-linked list:

1. remove the the node directly given a known predecessor
2. copy the value from the next node, then delete the next node (useful if the predecessor is unknown)

Because you already know the predecessor, I would advise to choose the first approach. I also like having a seperate method for unlinking a node; it can used for various list operations.

public ListNode unlinkNode(ListNode prev, ListNode cur)
{
 if (prev == null) {
 head = cur.next;
 } else {
 prev.next = cur.next;
 }
 return cur.next;
}
public ListNode RemoveElements(ListNode head, int val) {
 ListNode prevNode = null;
 ListNode current = head;
 while(current != null)
 {
 if (current.val == val) {
 current = unlinkNode(prevNode, current);
 } else {
 prevNode = current;
 current = current.next;
 }
 }
 return head;
}