这道题没有太多可说的,属于基本题的扩展。

可以先参考前面的 12. Remove Duplicates from Sorted List.

而这道题多出的一点把戏在于,要把重复的数据删的干干净净。我的策略很简单,将重复的数据做一个标记,isDuplicate, 然后再删掉重复元素的基础上,最后给剩下那个光棍补上一刀。

虽然有点啰嗦,但是效率还过得去。

#include <cstddef> 

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if (head == NULL) return head;
        ListNode preHead(0);
        preHead.next = head;
        ListNode *pre = &preHead;
        bool isDuplicate = false;
        ListNode *p = head;
        while (p->next)
            if (p->val == p->next->val) {
                ListNode *next = p->next->next;
                delete p->next;
                p->next = next;
                isDuplicate = true;
            } else if (isDuplicate) {
                ListNode *next = p->next;
                delete p;
                p = next;
                pre->next = p;
                isDuplicate = false;
            } else {
                pre = p;
                p = p->next;
            }
        if (isDuplicate) {
            ListNode *next = p->next;
            delete p;
            pre->next = next;
        }
        return preHead.next;
    }
};

LeetCode Direct Link