前往此题

解题思路

递归解法

这道题是很经典的链表题。先从阅读理解开始,题目的意思需要我们删除链表中所有重复的元素。对的,一个都不留,只要是这个元素涉及到重复了就删除。

这题我们先用递归来解这道题:

  1. 在这里递归的结束条件是headNone或者head.nextNone
  2. 如果head.val != head.next.val, 说明当前节点不是重复元素,需要保留,将head.next进入递归,检查head.next是否是重复节点。
  3. 如果遇到head.val == head.next.val,说明遇到了重复的节点,但这时我们不知道接下来还有多少个与head重复的节点,这个时候需要创建 一个辅助指针move,把move初始化在head.next节点,对move进行递归,如果head.val == move.val,则move移动到下一个节点,直到不重复为止,然后返回move。此时head.next必然是不重复的元素,这样重复的元素就删除了。
  4. 最后返回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(哑节点)同样也能用在这道题上

算法过程

  1. 初始化哑节点dummy,我们将dummy的下一个节点指向链表头head并赋值给pre用于操作
  2. 再初始化一个cur节点,思路和上面的解法一样,用于检查重复元素
  3. 开始遍历链表,如果cur.val == cur.next.val遇到重复元素,cur移动到下一个节点
  4. 如果没有遇到重复元素pre.next == cur,则pre移动到下一个节点
  5. 如果pre指针后面的全是重复元素,也就是说cur指针已经移动到了重复元素的末尾处,那pre.next = cur.next
  6. 最后返回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