203.移除链表元素

LeetCode LeetCode 链表 递归
发布时间 :
字数:1.5k 阅读 : 评论:
  1. 203.移除链表元素
    1. 203.1 题目
    2. 203.2 题解
      1. 虚拟头节点迭代法
      2. 递归法
    3. 203.3 代码
    4. 203.4 运行结果

203.移除链表元素

203.1 题目

给你一个链表的头节点 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

203.2 题解

虚拟头节点迭代法

// 方法一：虚拟头节点迭代法
// 创建虚拟头结点指向头结点进行遍历
// 判断当前节点的下一个节点的值是否等于指定值决定移动或者指向下下节点
// 直到当前节点的下一个节点为null
static ListNode RemoveElements1(ListNode head, int val)
{
    // 头结点为空直接返回
    if (head == null)
    {
        return null;
    }

    // 创建一个虚拟头节点，值为0，其next指向原链表的头节点
    ListNode preHead = new ListNode(0, head);

    // 初始化当前节点为虚拟头节点
    ListNode current = preHead;

    // 遍历链表，直到当前节点的下一个节点为null（即到达链表尾部）
    while (current.next != null)
    {
        // 判断当前节点的下一个节点的值是否等于指定值
        if (current.next.val != val)
        {
            // 如果不等于，将当前节点指向下一个节点，继续遍历
            current = current.next;
        }
        else
        {
            // 如果等于，将当前节点的下一个节点指向下下个节点，跳过中间节点
            current.next = current.next.next;
        }
    }

    // 返回虚拟头节点的下一个节点，即为新的头节点
    return preHead.next;
}

递归法

// 方法二：递归法
// 首先检查当前节点是否为空，若为空则说明已到达链表尾部，直接返回 null。
// 然后通过递归调用 RemoveElements2 方法处理当前节点的下一个节点。
// 最后，如果当前节点的值等于指定值，返回当前节点的下一个节点，即跳过当前节点。
static ListNode RemoveElements2(ListNode head, int val)
{
    // 如果当前节点为空，说明已到达链表尾部，返回null
    if (head == null)
    {
        return null;
    }

    // 递归调用 RemoveElements2 方法，处理当前节点的下一个节点
    head.next = RemoveElements2(head.next, val);

    // 如果当前节点的值等于指定值，返回当前节点的下一个节点，即跳过当前节点
    return head.val == val ? head.next : head;
}

203.3 代码

using System;

public class ListNode
{
    public int val;
    public ListNode next;

    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个链表的头节点 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 <= 50
        // 0 <= val <= 50

        #endregion

        #region 测试

        // 示例 1
        ListNode head1 = new ListNode(1,
            new ListNode(2, new ListNode(6, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6)))))));
        int val1 = 6;

        Console.Write("示例1 方法1 输出：");
        PrintLinkedList(RemoveElements1(head1, val1));

        Console.Write("示例1 方法2 输出：");
        PrintLinkedList(RemoveElements2(head1, val1));

        // 示例 2
        ListNode head2 = null;
        int val2 = 1;

        Console.Write("示例2 方法1 输出：");
        PrintLinkedList(RemoveElements1(head2, val2));

        Console.Write("示例2 方法2 输出：");
        PrintLinkedList(RemoveElements2(head2, val2));

        // 示例 3
        ListNode head3 = new ListNode(7, new ListNode(7, new ListNode(7, new ListNode(7))));
        int val3 = 7;

        Console.Write("示例3 方法1 输出：");
        PrintLinkedList(RemoveElements1(head3, val3));

        Console.Write("示例3 方法2 输出：");
        PrintLinkedList(RemoveElements2(head3, val3));

        #endregion
    }

    #region 答案

    // 方法一：虚拟头节点迭代法
    // 创建虚拟头结点指向头结点进行遍历
    // 判断当前节点的下一个节点的值是否等于指定值决定移动或者指向下下节点
    // 直到当前节点的下一个节点为null
    static ListNode RemoveElements1(ListNode head, int val)
    {
        // 头结点为空直接返回
        if (head == null)
        {
            return null;
        }

        // 创建一个虚拟头节点，值为0，其next指向原链表的头节点
        ListNode preHead = new ListNode(0, head);

        // 初始化当前节点为虚拟头节点
        ListNode current = preHead;

        // 遍历链表，直到当前节点的下一个节点为null（即到达链表尾部）
        while (current.next != null)
        {
            // 判断当前节点的下一个节点的值是否等于指定值
            if (current.next.val != val)
            {
                // 如果不等于，将当前节点指向下一个节点，继续遍历
                current = current.next;
            }
            else
            {
                // 如果等于，将当前节点的下一个节点指向下下个节点，跳过中间节点
                current.next = current.next.next;
            }
        }

        // 返回虚拟头节点的下一个节点，即为新的头节点
        return preHead.next;
    }


    // 方法二：递归法
    // 首先检查当前节点是否为空，若为空则说明已到达链表尾部，直接返回 null。
    // 然后通过递归调用 RemoveElements2 方法处理当前节点的下一个节点。
    // 最后，如果当前节点的值等于指定值，返回当前节点的下一个节点，即跳过当前节点。
    static ListNode RemoveElements2(ListNode head, int val)
    {
        // 如果当前节点为空，说明已到达链表尾部，返回null
        if (head == null)
        {
            return null;
        }

        // 递归调用 RemoveElements2 方法，处理当前节点的下一个节点
        head.next = RemoveElements2(head.next, val);

        // 如果当前节点的值等于指定值，返回当前节点的下一个节点，即跳过当前节点
        return head.val == val ? head.next : head;
    }



    #endregion

    #region 辅助方法

    static void PrintLinkedList(ListNode head)
    {
        while (head != null)
        {
            Console.Write($"{head.val} ");
            head = head.next;
        }

        Console.WriteLine();
    }

    #endregion
}

203.4 运行结果

示例1 方法1 输出：1 2 3 4 5 
示例1 方法2 输出：1 2 3 4 5 
示例2 方法1 输出：
示例2 方法2 输出：
示例3 方法1 输出：
示例3 方法2 输出：
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏