题目简述

        在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
        例如，链表1->1->2->3->3->4->4->5->5 处理后为 2->5

算法一: 非递归

时间复杂度：O(N)

思路：

        先将节点全部遍历一遍，存一下每个元素的值出现的个数；
        1. 如果该节点出现过，让 j 指针往后走；
        2. 如果没有出现过让上一个满足的 i 指向 j ，再用 i 保存这次满足的位置，即i=j，让j在继续往后走
        3.由于不确定最后满足一个位置的 i 的后面有没有自带往下指的指针，所以要将它指向NULL。

图解：


代码: 

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    unordered_map<int,int> hash;
    ListNode* deleteDuplication(ListNode* pHead) {
        if(!pHead) return NULL;
        ListNode* p=pHead;
        while(p){ // 记录每个值的个数
            hash[p->val]++;
            p=p->next;
        }
        ListNode* newHead=new ListNode(0);
        newHead->next=pHead;
        ListNode* i=newHead;
        ListNode* j=pHead;
        while(j){
            if(hash[j->val]>1){
                j=j->next; //如果该节点值个数大于1则往下走
            }
            else{
                i->next=j; //满足个数只有一个让i指向j
                i=j;    //保存该节点
                j=j->next;    //往下遍历
            }
        }
        i->next=NULL;
        return newHead->next;
    }
};


算法二:递归

时间复杂度：O(N)

思路:

        1. 找到以该节点为起点，第一个满足值不重复的节点。
        2. 让该节点指向下一个满足的节点
        这样就很容易通过递归实现，由于每次递归都能找到以该点为起点第一个不重复的节点，那么我们直接让第一个满足的节点a，使a->next指向从a->next开始下一个满足的节点。

代码: 

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead==NULL||pHead->next==NULL){ //若该节点为空或者只有一个节点则返回该节点
            return pHead;
        }        
        while(pHead && pHead->next && pHead->val==pHead->next->val){ //找到以该节点为其点第一个不重复的节点
            while(pHead && pHead->next && pHead->val==pHead->next->val){
                pHead=pHead->next;
            }
            pHead=pHead->next;
        }
        if(pHead) pHead->next=deleteDuplication(pHead->next); //使找到的那个节点指向下一个满足的节点
        return pHead;
    }
};