Leetcode 203.移除链表元素

1.题目描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

输入：head = [], val = 1
输出：[]

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

2.思路分析

2.1 递归

链表的定义具有递归的性质,题目 要求删除链表中所有节点值等于特定值的节点，可以用递归实现。

对于给定的链表:

• 首先对除了头节点 head 以外的节点进行删除操作, 然后判断 head 的节点值是否等于给定的 val
• 如果 head 的节点值等于 val，则 head 需要被删除，因此删除操作后的头节点为 head.next
• 如果 head 的节点值不等于val，则 head 保留，因此删除操作后的头节点还是 head

上述过程是一个递归的过程。

递归终止条件: head是否为空

• 如果head为空,直接返回head
• 如果head不为空,递归进行删除操作,然后判断head的节点值是否等于val,决定是否删除head

2.2 迭代法

cur:表示当前节点

• 如果cur 的下一个节点不为空且下一个节点的节点值等于给定的 val,则需要删除下一个节点,即为

  • cur.next = cur.next.next
    

• 如果cur的下一个节点不为空且下一个节点的节点值不等于给定的val,则下一个节点保留。

• 当cur的下一个节点为空时,链表的遍历结束,此时所有节点值等于val的节点君已经删除

实现: 设置虚拟头结点–> dummy_head = ListNode(next=head) 方便进行删除操作。

3.代码实现

3.1 递归

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if not head:
            return head
        head.next = self.removeElements(head.next, val)
        return head.next if head.val == val else head
1
2
3
4
5
6
7
8
9
10
11

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。递归过程中需要遍历链表一次。
• 空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用栈，最多不会超过 n 层。

3.2 迭代法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        # dummy_head -> 1->2->3->4->None val=2
        dummy_head = ListNode(next=head)
        cur = dummy_head
        while cur.next != None:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy_head.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。

空间复杂度：O(1)。