企业网站建设可行性青岛大学网站建设

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

题目要求

解题思路

一次遍历
由于给定的链表是排好序的，因此重复的元素在链表中的出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。
具体地，我们从指针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 headcur = headwhile cur.next:if cur.val == cur.next.val:cur.next = cur.next.nextelse:cur = cur.nextreturn head

复杂度分析

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