Easy

题目描述

给你一个链表的头节点 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, 10^4] 内
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

解题思路

这道题要求删除链表中所有值等于指定值的节点。主要有两种解法：

解法一：哨兵节点（推荐）

创建一个哨兵节点指向原链表头部，这样可以统一处理删除头节点和非头节点的情况。维护两个指针：prev指向待检查节点的前一个节点，curr指向当前检查的节点。如果当前节点值等于目标值，则让prev.next指向curr.next来删除当前节点；否则移动prev指针。

解法二：递归

递归地处理当前节点的后续链表，然后判断当前节点是否需要删除。如果当前节点值等于目标值，则返回处理后的后续链表；否则将当前节点连接到处理后的后续链表并返回。

解法三：直接遍历

不使用哨兵节点，先处理头部连续的目标值节点，然后遍历剩余链表删除目标节点。需要特别处理头节点的情况。

哨兵节点解法思路清晰，代码简洁，是最推荐的方法。

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;
        ListNode* curr = head;
        
        while (curr != nullptr) {
            if (curr->val == val) {
                prev->next = curr->next;
            } else {
                prev = curr;
            }
            curr = curr->next;
        }
        
        return 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 removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        curr = head
        
        while curr:
            if curr.val == val:
                prev.next = curr.next
            else:
                prev = curr
            curr = curr.next
        
        return dummy.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode RemoveElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        
        while (curr != null) {
            if (curr.val == val) {
                prev.next = curr.next;
            } else {
                prev = curr;
            }
            curr = curr.next;
        }
        
        return dummy.next;
    }
}

var removeElements = function(head, val) {
    let dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    let current = head;
    
    while (current !== null) {
        if (current.val === val) {
            prev.next = current.next;
        } else {
            prev = current;
        }
        current = current.next;
    }
    
    return dummy.next;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度哨兵节点解法递归解法
时间复杂度O(n)O(n)
空间复杂度O(1)O(n)
  • 时间复杂度：需要遍历整个链表一次
  • 空间复杂度：哨兵节点解法只使用常数额外空间；递归解法需要O(n)的调用栈空间

相关题目