139 删除链表中的重复元素II

问题描述：存在一个按照升序排列的链表，给你这个链表的头结点head，请你删除链表中所有存在数字重复情况的节点，只保留链表中没有出现的数字，返回的结果同样按升序的结果链表。

求解思路：双指针求解，定义两个指针开头均指向头结点，若下一个节点与当前节点不同，同时前进，若相同则第二个指针向前走，一直到遇到不同的节点，此时让第二个节点的next指向第二个指针，第一个指针前移，继续进行判断。直到都指向null。

public ListNode deleteDupItem(ListNode root)
{
ListNode first=root;
ListNode second=root;
while(first!=null&&second!=null)
{
if(first.next.val!=first.val)
{
first=first.next;
second=second.next;
}else
{
while(second!=null&&second.val==first.val)
{
second=second.next;
}
first.next=second;
first=first.next;
second=first;
}
}
???????return root;
}

递归求解：如果当前元素和下一个元素相同，则删除下一个元素，指向下下个元素，直到完全处理完毕。

public void dfs(ListNode root)
{
if(root==null){return;}
if(root.val==root.next.val&&root.next!=null)
{
root.next=root.next.next;
dfs(root.next);
}else if(root.next==null||root.val!=root.next.val)
{
dfs(root.next);
}
}
public ListNode Dfs(ListNode root)
{
dfs(root);
???????return root;
}

单指针求解：定义一个初始为root的单指针，如果该指针下一个指针指向为null，则表示处理完毕，若不为null，且相同，则该指针的next为next的next，否则前进。

public ListNode singlePoint(ListNode root)
{
ListNode single=root;
while(root!=null)
{
if(root.next==null){return root;}
if(root.val==root.next.val)
{
root.next=root.next.next;
}else
{
root=root.next;
}
}
???????return root;
}