专栏首页爱写BugLeetCode 203:移除链表元素

LeetCode 203:移除链表元素

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

Remove all elements from a linked list of integers that have value val.

示例:

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

解题思路:

两种方法,一种是迭代法,从第一个节点开始,遇到值相同的节点就将其删除。链表的删除操作是直接将删除节点的前一个节点指向删除节点的后一个节点即可。

第二种方法是递归,用递归从后向前遇到相同节点直接指向该节点的下一个节点的地址即可

迭代法:

由于链表删除操作的特殊性,如果要删除某个节点,必须要知道该删除节点的前一个节点地址才可完成删除操作。所以如果是从第一个节点开始判断,就要考虑到第一个节点是否为空节点、第一个节点是否就是该删除的的节点,删除头节点和非头节点的操作不一样,应单独实现删除操作。

如果原链表是这种形式:1->1->1->2 val=1 删除头节点后第二个节点置为头节点,但是第二个节点作为新的头节点依然需要删除,所以对头节点的操作应该是一个迭代过程。

另外一种方法就是新建一个虚拟节点,该虚拟节点下一个节点指向原链表头节点。这就无需考虑头节点是否为空、是否为待删除节点。如原链表为:1->1->1->2 val=1 ,新建一个虚拟节点 -1 作为头节点:-1->1->1->1->2 val=1 ,这时只需正常迭代删除即可,唯一要注意是返回节点不能是 head ,因为原链表的头节点如果是待删除节点,此时 head 节点已被删除并作为单独隔离出来的节点,并非链表内的一个节点。

Java:

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode newHead=new ListNode(-1);//新建虚拟节点
        newHead.next=head;//虚拟节点作为原链表的头节点
        ListNode cur = newHead;//遍历节点的指针

        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;//删除操作
            } else {
                cur = cur.next;
            }
        }
        return newHead.next;//返回的头节点应当是虚拟节点的下一个节点
    }
}

Python3:

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        newHead = ListNode(-1)
        newHead.next = head
        cur = newHead
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return newHead.next

递归法:

递归方法解该题很简单,基线条件是遇到空节点(最后一个节点),递归时只需将传递参数节点的下一个节点作为新的参数传给递归函数即可:

如原链表为:1->2->6->3->4->5->6, val = 6 递归到空节点时最后一个递归函数返回null:1->2->6->3->4->5->6->null 回到上一层递归函数内此时 head.next 得到返回节点 null 判断head为 6 删除,返回 head.next :1->2->6->3->4->5->null 回到上一层递归函数此时 head.next 得到上一层返回节点依然为null 判断head为 5 不删除,返回 head 为5:1->2->6->3->4->5->null 回到上一层递归函数此时 head.next 得到上一层返回节点 5 判断head为 4 不删除,返回 head 为4:1->2->6->3->4->5->null 回到上一层递归函数此时 head.next 得到上一层返回节点 4 …………..

直到回到第一个递归函数为止返回头节点结束。

Java:

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;//基线条件
        head.next = removeElements(head.next, val);
        if (head.val == val) {
            return head.next;
        } else {
            return head;
        }
    }
}

Python3:

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        if not head: return None
        head.next = self.removeElements(head.next, val)
        if head.val == val:
            return head.next
        else:
            return head

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 203:移除链表元素

    Remove all elements from a linked list of integers that have value val.

    爱写bug
  • LeetCode 206:反转链表 Reverse Linked List

    A linked list can be reversed either iteratively or recursively. Could you imple...

    爱写bug
  • LeetCode 206:反转链表 Reverse Linked List

    A linked list can be reversed either iteratively or recursively. Could you imple...

    爱写bug
  • LeetCode 203:移除链表元素

    Remove all elements from a linked list of integers that have value val.

    爱写bug
  • 图解精选 TOP 面试题 005.1 | 反转链表之递归求解

    在上一篇《图解精选 TOP 面试题 005 | 反转链表之迭代求解》中,我们介绍了该题的迭代求解法,本篇再说说如何进行递归求解。

    江不知
  • Java并发编程(七)ConcurrentLinkedQueue的实现原理和源码分析

    前言 我们要实现一个线程安全的队列有两种实现方式一种是使用阻塞算法,另一种是使用非阻塞算法。使用阻塞算法的队列可以用一个锁(入队和出队用同一把锁)或两个锁(入队...

    用户1269200
  • 【链表问题】环形单链表约瑟夫问题

    以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢

    帅地
  • 【链表问题】打卡9:将单链表的每K个节点之间逆序

    以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢。

    帅地
  • 《剑指offer》第11期:两个链表题目

    简单思路: 循环到链表末尾找到 length 在找到length-k节点 需要循环两次。

    ConardLi
  • 一天一大 leet(移除重复节点)难度:简单 DAY-26

    前端小书童

扫码关注云+社区

领取腾讯云代金券