# Remove all duplicated elements in a single list

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!

• A is really a terrible variable name. I'm sure you can think of something more meaningful. – t3chb0t Oct 11 '18 at 10:13
• I agree with you, and I already change the name. Thanks! – Nhan Phan Oct 11 '18 at 10:38
• Now the definition of the ListNode is gone ;-P – t3chb0t Oct 11 '18 at 10:41
• Oh, sorry! I fixed it. – Nhan Phan Oct 11 '18 at 12:25
• 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 '18 at 12:50

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.