题解 | #删除有序链表中重复出现的元素#
删除有序链表中重复出现的元素
http://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024
记住,是删除结点,所以至少需要三个指针,p、cur、q。可以设置一个yummyhead结点来保证循环的一致性,在循环的过程中,可以保证p结点和cur结点永远不相同,只比较cur和q即可。当cur和q相等时,用一个循环寻找第一个和cur不相等的q结点,让p结点指向q结点即可,这样就删除中间重复的cur结点,接下来如果q还存在,则指针后移。
class Solution { public: /** * * @param head ListNode类 * @return ListNode类 */ ListNode* deleteDuplicates(ListNode* head) { // write code here // 不要浪费时间了 求你了 // 删除重复元素 // 一遍扫描,记录第一次出现的元素,如果下一次元素不同,则更新,如果相同,则删除,所以同时要记录第一次出现元素之前的结点 if (!head || !head->next) { return head; } // 后插法要更简单一些 ListNode *yummyhead = new ListNode(-1); yummyhead->next = head; // 给链表加上伪头结点 ListNode *p = yummyhead; ListNode *cur = head, *q = head->next; yummyhead->next = head; while (q) { if (cur->val != q->val) { // 至少比较三个才能知道值是否是唯一出现的,可以保证p和cur一定不相等 // 相等,后移即可 p = cur; cur = q; q = q->next; } else { // 相等,就往后找直到找到第一个不相等的元素为止 while (q && cur->val == q->val) { q = q->next; } // 现在q和cur不相等 // 需要后移指针,将中间的结点都删除 // 判断到底是空退出的还是找到了第一个不相等的元素 p->next = q; if (q) { cur = q; q = q->next; } } // 可以保证p结点和cur结点不相等 } // 本来就不需要加入,你这把新建一个链表和删除链表中的值搞混了 return yummyhead->next; } ListNode *create(vector<int> vec) { ListNode* yummyhead = new ListNode(-1); ListNode* cur = yummyhead; for (int val : vec) { cur->next = new ListNode(val); cur = cur->next; } return yummyhead->next; } };