题目描述

给定一个有序链表，请删除其中的重复元素，使得原链表的元素仅出现一次。

样例1

输入：1->1->2
输出：1->2

样例2

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

算法

(线性扫描) $O(n)$

从前往后扫描整个链表，如果一个节点和其后继节点相同，则直接删除后继节点，否则指针移动到后继节点。

时间复杂度分析：整个链表只扫描一遍，所以时间复杂度是 $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) {
        if (!head) return head;
        ListNode* p = head;
        while (p->next)
        {
            if (p->val == p->next->val) p->next = p->next->next;
            else p = p->next;
        }
        return head;
    }
};