更多题解，请关注公众号：程序员学长，让你进大厂不走弯路

删除有序链表中重复的元素-I

问题描述

LeetCode 83. 删除排序链表中的重复元素

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次。

示例：

输入：{1,1,2}

输出：{1,2}

分析问题

因为给定的链表是排好序的，所以我们可以知道重复的元素在链表中出现的位置一定是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。

开始时，我们定义一个指针cur指向链表的头结点，然后开始对链表进行遍历。如果cur.val==cur.next.val时，我们就将cur.next这个节点从链表中移除；如果不相同，我们将指针cur后移，即cur=cur.next。当遍历完整个链表之后，我们返回链表的头结点即可。

下面我们来看一下代码的实现。

class Solution:
    def deleteDuplicates(self, head):
        #如果链表为空，直接返回
        if not head:
            return head
        #cur指向头结点
        cur = head
        #当cur.next不为空时
        while cur.next:
            #如果值相同，删除cur.next节点
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            #否则cur后移
            else:
                cur = cur.next
        return head

该算法的时间复杂度是O(N)，空间复杂度是O(1)。