题目描述

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次

样例

一、算法思路： 双指针算法

用两个指针，其中first指向第一个节点，然后second向后枚举，找到第一个与first不同的节点，然后将first指向second，随之first向后移动（移到second的位置）。

二、时间复杂度: 每个节点只被枚举了一遍，所以时间为O(n)

三、C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy -> next = head;
        auto first = dummy->next;
        while(first)
        {
            auto second = first;
            while(second && second->val == first->val)
            {
                second = second->next;
            }
            first -> next = second;
            first = second;
        }
        return dummy->next;

    }
};