LeetCode 题解工作台
移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 示例 1： 输入： head = [1,2,6,3,4,5,6], val = 6 输出： [1,2,3,4,5] 示例 2： 输入： head = [], …
2
题型
7
代码语言
3
相关题
当前训练重点
简单 · 链表指针操作
答案摘要
class Solution: def removeElements(self, head: ListNode, val: int) -> ListNode:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1 输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7 输出：[]
提示：
- 列表中的节点数目在范围
[0, 104]内 1 <= Node.val <= 500 <= val <= 50
解题思路
方法一
# 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 = ListNode(-1, head)
pre = dummy
while pre.next:
if pre.next.val != val:
pre = pre.next
else:
pre.next = pre.next.next
return dummy.next
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks for understanding of linked list pointer manipulation.
- question_mark
Tests ability to handle edge cases, including empty lists or lists where all nodes are removed.
- question_mark
Evaluates familiarity with both iterative and recursive solutions.
常见陷阱
外企场景- error
Failing to handle edge cases like an empty list or a list where no nodes match the value.
- error
Incorrectly updating the 'next' pointer when removing nodes, potentially causing cycles or missed nodes.
- error
Not considering the space complexity implications of recursion for large lists.
进阶变体
外企场景- arrow_right_alt
Implementing a solution where the target value is provided in reverse order.
- arrow_right_alt
Solving the problem with a doubly linked list where both 'next' and 'prev' pointers must be adjusted.
- arrow_right_alt
Modifying the list in place without using extra space for a new list or recursion.