Remove all duplicated elements in a single list

Question

I am learning algorithms. And my current algorithm is create a single list, and try to remove all duplicated elements in a sorted list. Ex: given Input: 1 -> 1 -> 1 -> 2 -> 2 -> 3 -> 5 -> 5 -> 7 Expected Output: 3 -> 7

My bellow solution worked well:

//Definition for singly-linked list.
public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int x)
    {
         val = x;
         next = null;
    }
}

public ListNode deleteAllDuplicates(ListNode list)
{
    if (list == null)
    {
        return null;
    }

    var start = list;
    var isStart = true;
    var pre = start;
    var tmp = list.val;

    while (list?.next != null)
    {

        if (tmp == list.next.val)
        {
            while (list?.val == tmp)
            {
                list = list.next;
            }

            if (isStart)
            {
                start = list;
                pre = start;
            }
            else
            {
                pre.next = list;
            }

            if (list == null)
            {
                return start;
            }

            tmp = list.val;
        }
        else
        {
            pre = list;
            list = list.next;
            tmp = list.val;
            isStart = false;
        }
    }

    return start;
}

My question is: What should I do to improve the solution? Any help are appriciate!

Answer 1

All in all it looks OK to me. I would maybe call the variables something else:

list -> root
tmp -> currentValue
start -> result
etc.

---

In the ListNode class it's common practice in C# to name public members in CamelCase:

public class ListNode
{
    public int Value;
    public ListNode Next;
    public ListNode(int x)
    {
         val = x;
         next = null;
    }
}

---

I think that the null-conditional operator is unnecessary in the outer loop.

---

My own version would look something like:

public static ListNode RemoveDuplicates(ListNode root)
{
  ListNode current = root;
  ListNode result = null;
  ListNode prev = null;

  while (current != null)
  {
    bool singleFound = true;

    while (current?.val == current?.next?.val)
    {
      current = current.next;
      singleFound = false;
    }

    if (singleFound)
    {
      if (result == null)
      {
        result = prev = current;
      }
      else
      {
        prev.next = current;
        prev = prev.next;
      }
    }

    current = current?.next;

    if (singleFound && prev != null)
      prev.next = null;
  }

  return result;
}

---

Some other considerations:

The name is maybe ambiguous:

My first thought was that it should remove all but one entry per value:

{ 1, 1, 2, 3, 4, 5, 5, 7, 7 } -> { 1, 2, 3, 4, 5, 7 }

---

Normally I would prefer that a static method/function would leave the argument list untouched, but you actually operate on the nodes in the list directly and return a new ListNode as root of the resulting list. So the original list is in an indefinite state when the function returns.

My own implementation modified to handle that:

public static ListNode RemoveDuplicates(ListNode root)
{
  ListNode current = root;
  ListNode result = null;
  ListNode prev = null;

  while (current != null)
  {
    bool singleFound = true;

    while (current?.val == current?.next?.val)
    {
      current = current.next;
      singleFound = false;
    }

    if (singleFound)
    {
      if (result == null)
      {
        result = prev = new ListNode(current.val);
      }
      else
      {
        prev.next = new ListNode(current.val);
        prev = prev.next;
      }
    }

    current = current?.next;
  }

  return result;
}

If you had a class like:

public class SortedLinkedList
{
  public void DeleteDuplicates()
  {
    ...
  }
}

I would on the other hand expect DeleteDuplicates() to operate on the current instance.