给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
解法:
遇到当前与之后重复就跳过中间元素,以node.next为循环判断方式
循环解法
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
node=head
while node.next: #node.next
if node.val==node.next.val:
temp=node.next
node.next=temp.next
else:
node=node.next
return head
递归解法
递归解法实际上一直在比较递归栈中的head和head.next
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
head.next=self.deleteDuplicates(head.next)
if head.val==head.next.val: #用头结点比较
head=head.next
return head
使用python的set记录值可以解决无序的重复元素删除
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
record=set()
node=head
while node.next:
record.add(node.val)
if node.next.val in record:
node.next=node.next.next
else:
node=node.next
return head