题目
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
示例 1:
输入:head = [1,1,2] 输出:[1,2] 示例 2:
输入:head = [1,1,2,3,3] 输出:[1,2,3]
提示:
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100 题目数据保证链表已经按升序 排列
思路1
模拟题目中的要求,遍历整个链表,如果当前节点和下一个节点数值相同,则删除下一个节点,,注意要事先保存头节点,最后返回头节点即可
复杂度
时间复杂度:
我们只遍历一遍链表,第二个while循环删除节点,并不是遍历 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]: node = head while head and head.next: while head.next and head.val == head.next.val: head.next = head.next.next head = head.next return node
思路2
使用快慢指针,快指针遍历所有节点,如果快指针的值和慢指针不同,说明找到了不同的节点,然后将slow节点后面的节点赋值fast即可
我们最后一次赋值的时候,如果此时的fast节点后面仍然有值,则slow后面也会带着,所以最后要切断slow后面的节点
复杂度
时间复杂度:
依旧只遍历一遍链表 O ( n ) O(n)O(n)
空间复杂度:
O ( 1 ) O(1)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 not head:return head fast,slow = head,head while fast: if slow.val != fast.val: slow.next = fast slow = slow.next fast = fast.next slow.next = None return head