题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留。

样例1

输入：1->2->3->3->4->4->5

输出：1->2->5

样例2

输入：1->1->1->2->3

输出：2->3

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;

        map<int, int> m;
        ListNode* p = head;
        //将每个数字出现的次数统计出来
        while(p != NULL)
        {
            m[p->val]++;
            p = p->next;
        }

        //分为前后指针，好进行删除操作
        ListNode* hh = head;
        ListNode* tt = head->next;

        while(tt != NULL)
        {
            //取出结点tt
            if(m[tt->val] > 1) hh->next = tt->next; //当前结点出现多次,将hh结点指针指向tt的下一个结点
            else hh = hh->next; //tt结点只出现一次，hh向后移动

            //tt向后移动
            tt = tt->next;
        }
        //如果剩下的第一个结点也是出现多次的，分只剩下一个和多个的情况
        if(m[head->val] > 1)
        {
            if(head->next == NULL) return NULL; //只剩下一个直接返回
            else head = head->next; //向后挪动一个位置进行返回
        }
        return head;
    }
};