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

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) 
{
    if(NULL == head || NULL == head->next)
        return head;
    
    int val = head->val;
    struct ListNode *p = head->next;
    struct ListNode *tmp = NULL;
    if(p->val != val)
    {
        head->next = deleteDuplicates(p);
        return head;
    }
    else
    { 
        while(p && p->val == val)
        {
            tmp = p;
            /*free p ,if necessary*/
            free(p);
            
            p = p->next;
        }
        return deleteDuplicates(p);
        
    }
    
}

看了讨论区大神的java代码，用递归的方式实现，是我没有想到的。非常的巧妙。
一般实现方法是通过一个二级指针来实现，比如链表元素 1 ,1 ,1 , 2 ,3 ,4,5,5,5开始p保存的是头节点的地址，然后进入第二个循环，循环结束此时p2指向2，因为p2!=p1->next,表示要改变头结点即*p = p2(*p就是head，此时相当于head = p2),然后继续执行p1指向2，p2指向3，内层while循环结束，进入else的分支，此时不应改变头结点，因此二级指针中存的是下一个节点的地址是下一个要判断是否重复的节点的指针的地址，然后2！=3，并且p1->next ==p2，重复上一步骤将p 置为下一个要判断是否重复的节点的指针的地址。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* deleteDuplicates(struct ListNode* head) 
{
     struct ListNode** p = &head;
    
     struct ListNode *p1 = NULL;
     struct ListNode *p2 = NULL;
     
     struct ListNode * tmp = NULL;
     struct ListNode * fun = NULL;
    
     while(*p && (*p)->next) 
     {
         p1 = *p, p2 = p1->next;
         while(p2 && p2->val == p1->val) 
         {
             /*free memory,if necessary*/
             p2 = p2->next;
         }
         if(p2 != p1->next) 
         {
             *p = p2;
         } 
         else 
         {
             p = &(p1->next);
         }
    }
    
    return head;
}

递归的实现非常好理解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return nullptr;
        if(!head->next) return head;
        ListNode* p = head->next;
        int val = head->val;
        if(p->val != val)
        {
            head->next = deleteDuplicates(p);
            return head;
        }else{
            while(p && p->val == val)
            {
                p = p->next;
            }
            return deleteDuplicates(p);
        }
        
    }
};

非递归解法，非常好理解的C++代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head || !head->next)
            return head;
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* prev = dummy,*current = head;
        while(current)
        {
            while(current->next &&
              prev->next->val == current->next->val)
                current = current->next;
            
            if(prev->next == current)
                prev = prev->next;
            else
                prev->next = current->next;
            
            current = current->next;
            
        }
        ListNode* new_head = dummy->next;
        delete dummy;
        return new_head;
    }
};

运行效率:

Runtime: 8 ms, faster than 57.69% of C++ online submissions for Remove Duplicates from Sorted List II.
Memory Usage: 11.2 MB, less than 17.49% of C++ online submissions for Remove Duplicates from Sorted List II.