标签: 链表
难度: Easy
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2] 输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3] 输出：[1,2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
Submission
运行时间: 44 ms
内存: 15 MB
# 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: Optional[ListNode]) -> Optional[ListNode]:
if head is None:
return head
cur = head
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
Explain
这个题解采用了一次遍历链表的方法。遍历过程中，如果当前节点和下一个节点的值相同，就将当前节点的 next 指针指向下一个节点的 next，这样就删除了重复的节点。如果当前节点和下一个节点的值不同，就将当前节点后移。遍历直到当前节点为空，表示处理完了整个链表。最后返回链表的头节点 head。
时间复杂度: O(n)
空间复杂度: O(1)
# 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: Optional[ListNode]) -> Optional[ListNode]:
# 如果链表为空，直接返回
if head is None:
return head
# 初始化当前节点指针 cur 为头节点
cur = head
# 遍历链表，直到当前节点 cur 为空
while cur and cur.next:
# 如果当前节点和下一个节点的值相同
if cur.val == cur.next.val:
# 删除下一个节点，将当前节点的 next 指向下一个节点的 next
cur.next = cur.next.next
# 如果当前节点和下一个节点的值不同
else:
# 将当前节点后移
cur = cur.next
# 返回删除重复节点后的链表头节点
return head
Explore
如果链表只有一个元素，该元素自然没有下一个节点来比较，因此`cur.next`为`None`，循环体不会执行，直接返回原链表头节点，即单个元素。如果链表中的所有元素都不相同，每次比较`cur.val`和`cur.next.val`都不会相等，因此`cur`指针会一直后移，直到链表末尾，循环结束后返回的还是原链表头节点。在这两种情况下，链表都不会被修改。
在循环条件中只检查`cur.next`的存在性是因为`cur`的存在性在每次循环的开始已经隐含地被检查了。由于循环是从头节点开始，且每次迭代结束时，如果`cur.next`不存在（即`cur`是尾节点或后面没有节点），循环会自然结束。如果同时检查`cur`和`cur.next`的存在性，实际上是多余的，因为当`cur`为`None`时，循环已经无法继续。
不需要进行额外的操作来确保链表的排序状态。算法的逻辑保证了只有连续且相同的元素会被删除，不会对原有的排序顺序产生影响。因为链表本身是预先排序的，删除操作只是去除了重复的元素，未改变非重复元素间的相对顺序。
是的，这个方法能有效地删除所有重复的节点。当遇到连续的重复元素时，例如`[1,1,1,2]`中的三个`1`，`cur`指针所指的节点的`val`与`cur.next.val`相同，因此会持续更新`cur.next`为`cur.next.next`，直到`cur.next`指向的节点值不再与`cur.val`相同。这样，所有连续重复的节点都会被删除，只留下一个`1`。