Description
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现的数字。
Analyze
链表操作，删除一个有序链表中的所有重复元素。
给定函数如下:
- @param head 链表的头结点(带数据)
首先考虑特殊情况:
- 给定的链表为空
- 给定的链表只有一个元素
上述两种都是特殊情况，但在此题处理方法都是一样的，即返回给定的链表
然后考虑一般情况:
比较发现当前结点和下一结点值相同时，应当把当前结点和下一结点一起排除在外，即当前结点也是要删除的对象，因此需要知道当前结点的前驱结点，注意， 此前驱结点并不是当前结点的 直接前驱结点，而是原表中没有出现重复的结点。
这里又有一个新的问题出现了，就是当判断出第一个元素和第二个相等时，应当把这两个元素一起排除，此时有两种解决方法:
- 一种是直接把头结点的值和 next 指向的地址一起修改，即把整个 head 修改成符合条件的结点，并作为要返回的链表的头结点
- 还有一种是给原来的链表设定一个头指针 h ，此时只要修改 h->next 为新的节点就行了，返回时返回 h->next
显然。上述两种方法都是可行的，但是在实际编程的时候会发现，第一种不能写入遍历链表的循环中，要单独写出来，甚至要单独写一个循环来判断新的链表头结点在何处，因此下面我们采用第二种方法。
解决了这些看起来是小问题的问题，这道题其实就已经做出来一半了，主要思路是通过比较 head，moveNode 两个指针指向的数据来判断哪个结点应该保留，并把它放到 h所指向的链表中去。
Realization
-
特殊情况处理
- 定义三个重要的指针并初始化
h 定义为结构体是为了方便，可以不用为它开辟空间，让它指向 NULL 而不是 head 是为了把所有情况考虑在内，比如如果所有的元素都有重复，此时应该返回的是 NULL 而不是第一个结点。
- 主要算法
- 比较到不同，加入链表
pre->next = NULL 是为了切断新链表和旧链表的联系
- 相同时的处理方法
当发现重复元素时，把 moveNOde 一直移动到第一个不重复的结点，再重新判断
- 后续改进
这里再进行一次判断是因为，当之前定位到第一个不重复的元素后，实际 head 指向这个元素，而 moveNode 是指向下一个元素的，因此，此时若是 moveNode 为空的话，那么 head 所指向的元素也是满足条件的，要把它加入到链表当中
- 最后返回新链表头结点
提交
Dictionary
上述解法看起来是循环中嵌套了循环，复杂度应该很高，但仔细思考会发现，其实复杂度还是O(n)，因为最外层循环是 while(moveNode) ，即遍历链表，内层循环的作用是从当前结点往后找到第一个不相等的元素，移动的指针也是 moveNode ，所以循环的次数就是链表中的所有结点个数，最后 moveNode 为空时会跳出所有循环
附源代码
/*
* @lc app=leetcode.cn id=82 lang=c
*
* [82] 删除排序链表中的重复元素 II
*/
// @lc code=start
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteDuplicates(struct ListNode* head){
if(!head || !head->next)
{
return head;
}
struct ListNode h, *moveNode = head->next;
h.next = NULL;
struct ListNode* pre = &h;
while(moveNode)
{
if(head->val != moveNode->val)
{
pre->next = head;
pre = pre->next;
pre->next = NULL;
}
else
{
while(moveNode && head->val == moveNode->val)
{
moveNode = moveNode->next;
}
if(!moveNode)
{
break;
}
}
head = moveNode;
moveNode = moveNode->next;
if(!moveNode)
{
pre->next = head;
pre = pre->next;
pre->next = NULL;
break;
}
}
return h.next;
}
// @lc code=end
