Problem: 82. 删除排序链表中的重复元素 II
文章目录
- 思路
- 解题方法
- 复杂度
- Code
思路
遍历
解题方法
这题最大的特点就是要删除所有重复的元素
因为涉及到头节点是重复元素的情况,所以需要设置一个虚拟的头结点dummy
利用cur代表当前位置的指针
if cur.next.val == cur.next.next.val:
# 需要删除所有重复的元素,这里用tem指向cur.next
tem = cur.next
# 不断判断tem.val与tem.next.val的关系,然后删除所有重复的元素
while tem.val == tem.next.val:
tem = tem.next # 此时cur还在原地
cur.next = tem.next # 指向tem的下一个位置
else:
cur = cur.next
复杂度
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
Code
# 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]:
dummy = ListNode(val=-1, next=head) # 虚拟节点
cur = dummy
while cur.next and cur.next.next:
if cur.next.val == cur.next.next.val:
tem = cur.next
while tem.next and tem.val == tem.next.val:
tem = tem.next
cur.next = tem.next
else:
cur = cur.next
return dummy.next