算法四十天-删除排序链表中的重复元素

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

题目要求

解题思路

一次遍历
由于给定的链表是排好序的，因此重复的元素在链表中的出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。
具体地，我们从指针cur指向链表的头节点，随后开始对链表进行遍历。如果cur.val == cur.next.val，可以直接将cur后移一位，移除值相同的链表。
当遍历完整这个链表时，返回链表的头节点就可以了

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        cur = head
        while cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

复杂度分析

时间复杂度：$O(N)$
空间复杂度：$O(1)$