解题思路
递归解法
这道题是很经典的链表题。先从阅读理解开始,题目的意思需要我们删除链表中所有重复的元素。对的,一个都不留,只要是这个元素涉及到重复了就删除。
这题我们先用递归来解这道题:
- 在这里递归的结束条件是
head
为None
或者head.next
为None
- 如果
head.val != head.next.val
, 说明当前节点不是重复元素,需要保留,将head.next
进入递归,检查head.next
是否是重复节点。 - 如果遇到
head.val == head.next.val
,说明遇到了重复的节点,但这时我们不知道接下来还有多少个与head
重复的节点,这个时候需要创建 一个辅助指针move
,把move
初始化在head.next
节点,对move
进行递归,如果head.val == move.val
,则move
移动到下一个节点,直到不重复为止,然后返回move
。此时head.next
必然是不重复的元素,这样重复的元素就删除了。 - 最后返回
head
代码
class Solution(object):
def deleteDuplicates(self, head):
if not head or not head.next:
return head
if head.val != head.next.val:
head.next = self.deleteDuplicates(head.next)
else:
move = head.next
while move and head.val == move.val:
move = move.next
return self.deleteDuplicates(move)
return head
双指针解法
链表中常用的一个技巧dummy
(哑节点)同样也能用在这道题上
算法过程
- 初始化哑节点
dummy
,我们将dummy
的下一个节点指向链表头head
并赋值给pre
用于操作 - 再初始化一个
cur
节点,思路和上面的解法一样,用于检查重复元素 - 开始遍历链表,如果
cur.val == cur.next.val
遇到重复元素,cur
移动到下一个节点 - 如果没有遇到重复元素
pre.next == cur
,则pre
移动到下一个节点 - 如果
pre
指针后面的全是重复元素,也就是说cur
指针已经移动到了重复元素的末尾处,那pre.next = cur.next
- 最后返回
dummy.next
代码
# 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 head
dummy = ListNode(0)
dummy.next = head
pre = dummy
cur = head
while cur:
while cur.next and cur.val == cur.next.val: cur = cur.next
if pre.next == cur: pre = pre.next
else: pre.next = cur.next
cur = cur.next
return dummy.next