LeetCode 203：移除链表元素 Remove LinkedList Elements

makeFoxPlay 发布于2019-07-31 11:28 / 2714人阅读

摘要：删除链表中等于给定值的所有节点。链表的删除操作是直接将删除节点的前一个节点指向删除节点的后一个节点即可。这就无需考虑头节点是否为空是否为待删除节点。

删除链表中等于给定值 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

GPU云服务器云服务器移除元素移除数组元素 js 数据移除元素 js数组如何移除元素

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/45178.html

LeetCode 203：移除链表元素 Remove LinkedList Elements

摘要：删除链表中等于给定值的所有节点。链表的删除操作是直接将删除节点的前一个节点指向删除节点的后一个节点即可。这就无需考虑头节点是否为空是否为待删除节点。删除链表中等于给定值 val 的所有节点。 Remove all elements from a linked list of integers that have value val. 示例: 输入: 1->2->6->3->4->5-...

hzc 2019-08-16 18:37 评论0 收藏0
LeetCode【203】：移除链表元素

摘要：题目描述删除链表中等于给定值的所有节点。示例输入输出非递归解法思路遍历链表，找出每个待删除节点的前一个节点。特殊情况第一个节点就是待删除节点时，要单独操作。注意点当输入为时，按上面的思路删除第一个节点，剩下的链表的头节点又是待删除节点。题目描述删除链表中等于给定值 val 的所有节点。示例输入: 1->2->6->3->4->5->6, val = 6输出: 1->2->3->...

wwolf 2019-08-19 11:38 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
移除链表倒数第n个元素

摘要：移除链表倒数第个元素给定一个链表，移除倒数第个元素，返回链表头部。移除链表倒数第n个元素 Remove Nth Node From End of List 给定一个链表，移除倒数第n个元素，返回链表头部。 Given a linked list, remove the nth node from the end of list and return its head. Note:...

yhaolpz 2019-07-25 12:04 评论0 收藏0