203.删除链表中的节点

发表于 更新于 分类于 ，

题目

删除链表中等于给定值 val 的所有节点。

示例:

1
2
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

思路

这道题可以用两种解法解决.

  • 直接用最普通的循环方法,在一个循环内判断链表中的某个数是否与val相同,然后删去相同节点.
  • 用递归方法来解决.

这里重点讲解一下递归解决这道题的思路.

首先我们用递归函数的时候,要明确的知道这个函数是干嘛的,并且坚信它已经可以实现这个功能,所以到了这道题,首先我们要明确知道,这个题目要求的方法是"删除链表中定值等于val的节点,并且返回删除后的链表".所以我们可以得到下面这个函数:

1
2
3
public ListNode RemoveElements(ListNode head, int val)
{
}

我们先不管里面是怎么实现的,现在我们要做的是坚信这个函数已经实现了这个功能.

然后,我们要找出递归函数的出口,即终止条件,也就是说当递归到了什么程度的时候,可以结束.

可以想到,当head到了最小情况,也就是为null的时候,可以直接返回null结束了.所以head==null就是终止条件:

1
2
3
4
5
6
7
public ListNode RemoveElements(ListNode head, int val)
{
    if (head == null)
    {
        return null;
    }
}

接下来,我们就要将问题逐步分解为子问题,将递归范围逐步减小.

想一下,如果一条长度为4个节点的链表,放入我们的函数,将会如何操作.注意这个时候不要想递归是如何实现的,而是要坚信现在的函数已经可以实现这个功能了.

这个时候会有两种情况:

  1. 这个4个节点的链表的第一个节点就是要删除的节点.这个时候我们只要放弃掉第一个节点,将剩下的三个节点作为一条新的链表,继续放入我们的函数中进行判断即可.所以现在代码应该是这样的:
1
2
3
4
5
6
7
8
9
10
11
public ListNode RemoveElements(ListNode head, int val)
{
    if (head == null)
    {
        return null;
    }
    if (head.val == val)//如果是要删除的.
    {
        return RemoveElements(head.next, val);//那就把第一个节点扔掉,将剩下的三个节点作为一个新的链表,继续放入函数判断.
    }
}
  1. 这个4个节点的链表的第一个节点不是我们要删除的节点,这个时候我们保留第一个节点,将剩下的的3个节点作为一个新的链表,继续放入函数中进行判断.这个时候代码就会成为这样:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode RemoveElements(ListNode head, int val)
{
    if (head == null)
    {
        return null;
    }
    if (head.val == val)
    {
        return RemoveElements(head.next, val);
    }
    else
    {
        head.next = RemoveElements(head.next, val);//保留第一个节点head,将剩下的三个节点作为一个新的链表放入函数进行判断,并且将结果接到头节点后面.
    }
    return head;
}

到了这里,整个递归就已经完成了.

代码

普通循环法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode RemoveElements(ListNode head, int val)
{
    ListNode p = new ListNode(-1)
    {
        next = head
    };
    ListNode h = p;
    while (p.next != null)
    {
        if (p.next.val == val)
        {
            p.next = p.next.next;
            continue;
        }
        p = p.next;
    }
    return h.next;
}

递归法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode RemoveElements(ListNode head, int val)
{
    if (head == null)
    {
        return null;
    }
    if (head.val == val)
    {
        return RemoveElements(head.next, val);
    }
    else
    {
        head.next = RemoveElements(head.next, val);
    }
    return head;
}