29. 删除链表中重复的节点

题目

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

数据范围
链表中节点 val 值取值范围 [0,100]。
链表长度 [0,100]。

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

输出：1->2->5
样例2
输入：1->1->1->2->3

输出：2->3

代码

• 因为头节点都可能被删掉，所以创建一个虚拟头节点指向head，过程中就不用处理第一次插入节点时的判断操作，最终返回虚拟节点的next即可
• 双指针遍历链表

/** * 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 || !head->next)return head;//如果链表为空或只有一个节点，则之间return head
        ListNode * pre = head, *cur = head, *ans = new ListNode(-1);//虚拟节点
        ListNode * tail = ans; //操作链表的尾指针
        while(cur){
    //当没有遍历到NULL时，一直遍历链表
            int cnt = 0;//统计pre和cur节点中有多少个重复的节点
            //当cur不为空并且前后指针的值相同时，一直移动cur指针并且cnt++
            while(cur && pre->val == cur->val)cur = cur->next, cnt++;
            if(cnt <= 1){
    //如果没有pre跟cur之间的节点值没有重复
                tail->next = pre;//把pre节点插入到tail后面
                tail = tail->next;//更新tail尾指针
                pre = cur;//把pre重新置于跟cur同一个位置
            }else{
    //如果有重复
                if(!cur)tail->next = NULL;//当此时是在链表末尾出现重复，则更新tail->next为NULL，下次再进入循环时cur为空会结束循环
                pre = cur;//把pre重新置于跟cur同一个位置
            }
        }
        return ans->next;//返回虚拟节点的next
    }
};