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!

  • 2
    A is really a terrible variable name. I'm sure you can think of something more meaningful. – t3chb0t Oct 11 at 10:13
  • I agree with you, and I already change the name. Thanks! – Nhan Phan Oct 11 at 10:38
  • 2
    Now the definition of the ListNode is gone ;-P – t3chb0t Oct 11 at 10:41
  • Oh, sorry! I fixed it. – Nhan Phan Oct 11 at 12:25
  • 2
    Your code doesn't work for inputs with non-consecutive duplicates, such as [1, 2, 1]. If this is only intended to work with sorted inputs then you may want to explicitly say so. – Pieter Witvoet Oct 11 at 12:50
up vote 2 down vote accepted

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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.