Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,

Given 1->2->3->3->4->4->5, return 1->2->5.

Given 1->1->1->2->3, return 2->3.

1         public static LinkedListNode RemoveDuplicatesfromSortedListIIOpt(LinkedListNode head) 2         { 3             if (head == null || head.Next == null) 4                 return head; 5  6             LinkedListNode fakeHead = new LinkedListNode(); 7             LinkedListNode prev = fakeHead; 8             prev.Next = head; 9             LinkedListNode curr = head;10 11             while (curr != null && curr.Next != null)12             {13                 //curr Node has duplicated14                 if ((int)curr.Value == (int)curr.Next.Value)15                 {16                     //find the next Node, which value != curr.value17                     int temp = (int)curr.Value;18                     curr = curr.Next;19                     while (curr != null && (int)curr.Value == temp)20                     {21                         curr = curr.Next;22                     }23                     prev.Next = curr;24                 }25                 //curr Node has no duplicated26                 else27                 {28                     prev = prev.Next;29                     curr = curr.Next;30                 }31             }32 33             return fakeHead.Next;34         }

代码分析：

　　这一题稍稍有点tricky。我还是创建了一个fakeNode，用来连接head，返回的时候返回fakeHead.Next, 这样下面的逻辑就适合所有的Node了，而不用去特殊处理第一个Node就有duplicate 的 corner case。

　　这种题虽然是BF，没什么好复习的，但是还是要小心再小心，不容易写出BUG FREE的CODE。