题目描述
在一个排序的链表中，存在重复的节点，请删除该链表中重复的节点，重复的节点不保留。
数据范围
链表中节点 val 值取值范围 [0,100]。
链表长度 [0,100]。
样例1
输入：1->2->3->3->4->4->5 输出：1->2->5
样例2
输入：1->1->1->2->3 输出：2->3
方法一：线性扫描 O(n)
这题我们可以创建一个新的头结点出来，方便我们去处理后续结点。但是，我们下面演示操作的时候是直接在链表上进行处理，这样大家能够看得更清楚一些。
然后我们分两种情况来讨论，分别是出现重复结点的情况和无重复结点的情况。
情况一： 出现重复结点时，我们会用一个指针 q 去找到下一个值。
可以用 while 循环进行查找，找到直到与 p->next 的值不同为止。
情况二： 当前遍历的是不重复的结点，还是进行同样的判断操作。
由于没有重复的元素， q 经过 while 循环后只会向后移一位。所以 p->next->next 就是 q ，故直接将 p 往后移一位即可。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* deleteDuplication(ListNode* head) { ListNode* dummy = new ListNode(-1); dummy->next = head; ListNode* p = dummy; while (p->next) { ListNode* q = p->next; while (q && p->next->val == q->val) q = q->next; if (p->next->next == q) p = p->next; //没有重复元素 else p->next = q; //有重复元素 } return dummy->next; } };
欢迎大家在评论区交流~
