题解 | #删除有序链表中重复的元素-II#
删除有序链表中重复的元素-II
https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ ListNode* deleteDuplicates(ListNode* head) { // write code here if (head == NULL)return NULL; if (head->next == NULL)return head; ListNode* newhead = new ListNode(0); newhead->next = head; ListNode* rec = newhead, * pre = head, * back = head->next; while (back) { if (pre->val == back->val) { while (1) { if (back == NULL)break; if (pre->val == back->val)back = back->next; else break; } pre->next = back; rec->next = back; } else rec = rec->next; pre = pre->next; if (back)back = back->next; } return newhead->next; } };
三指针(双指针的思路):跟上一题的思路一样,只不过现在需要将pre指向的结点的上一个结点连接到back指向的结点,所以可以用一个新指针用于记录pre的上一个位置。这里为了方便编写,用了一个技巧,即先在head结点前加一个新的头节点,这样就能将head结点为重复元素的情况隐式地包括进去。
时间复杂度On,空间复杂度为常数。