Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3

AC代码

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !(head->next)) return head;
        ListNode *nope = new ListNode(-1), *ret = nope;
        nope->next = head;
        ListNode* pre = head;
        head = head->next;
        while (head) {
            if (pre->val != head->val) {
                head = head->next;
                pre = pre->next;
                nope = nope->next;
            }
            else {
                while (head->next && head->next->val == head->val) {
                    head = head->next;
                    pre = pre->next;
                }
                nope->next = head->next;
                if (head->next && head->next->next) {
                    pre = head->next;
                    head = head->next->next;
                }
                else break;
            }
        }
        return ret->next;
    }
};

优化代码

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *pre = new ListNode(-1), *ret = pre;
        pre->next = head;
        while (pre->next) {
            head = pre->next;
            while (head->next && head->next->val == head->val)
                head = head->next;
            if (head == pre->next)
                pre = pre->next;
            else
                pre->next = head->next;
        }
        return ret->next;
    }
};

递归代码

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !(head->next)) return head;
        ListNode* p = head->next;
        if (p->val != head->val) {
            head->next = deleteDuplicates(p);
            return head;
        }
        else {
            while (p && p->val == head->val) p = p->next;
            return deleteDuplicates(p);
        }
    }
};

总结

一开始自己写的循规蹈矩，同时移动三个指针，效率上很低，很憨憨，稍微改进了一下好很多。递归代码参考：https://www.cnblogs.com/AndyJee/p/4467051.html