题目链接：leetcode82

题目大意

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。 示例一： 输入: 1->2->3->3->4->4->5 输出: 1->2->5 示例二： 输入: 1->1->1->2->3 输出: 2->3

简而言之就是删掉原始序列中，所有出现次数大于1的元素。

解题思路

直接删除

AC 的代码就是这个方法，但逻辑可能略显冗余。先建一个头节点使链表变成带头节点的单链表。然后就是p、q两个指针分别表示相邻两种元素，如果发现靠后的指针的下一个节点有重复，那么就一直删掉，最后一个元素最后特判删除。

时间复杂度 $O(n)$， 空间复杂度 $O(1)$。

代码实现

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* deleteDuplicates(ListNode* head) { ListNode *q, *p, *h = new ListNode(0); bool flag; h->next = head; q = h; p = head; while (p && p->next) { flag = true; while (p->next && p->val == p->next->val) { p = p->next; delete q->next; q->next = p; flag = false; } if (flag) { q = p; p = p->next; } else { p = p->next; delete q->next; q->next = p; } } return h->next; } };