LeetCode【203】：移除链表元素

wwolf 发布于2019-08-19 11:38 / 3477人阅读

摘要：题目描述删除链表中等于给定值的所有节点。示例输入输出非递归解法思路遍历链表，找出每个待删除节点的前一个节点。特殊情况第一个节点就是待删除节点时，要多带带操作。注意点当输入为时，按上面的思路删除第一个节点，剩下的链表的头节点又是待删除节点。

题目描述

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

示例

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

非递归解法 思路

遍历链表，找出每个待删除节点的前一个节点。
特殊情况：第一个节点就是待删除节点时，要多带带操作。
注意点：当输入为：[1,1]时，按上面的思路删除第一个节点，剩下的链表的头节点又是待删除节点。

    public ListNode removeElements(ListNode head, int val) {
        while(head != null && head.val == val){
            ListNode pre = head;
            head = pre.next;
            pre.next = null;
        }
            
        if(head == null){
            return null;
        }
        ListNode pre = head;
        while(pre.next!=null){
            ListNode cur = pre.next;
            if(cur.val == val){
            pre.next = cur.next;
            cur.next = null;
            }else{
                pre = pre.next;
            }    
        }
        return head;
        
    }

使用虚拟头结点（统一头节点和其他节点的操作）简化代码:

    private class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        while(pre.next!=null){
            ListNode del = pre.next;
            if(del.val == val){
            pre.next = del.next;
            del.next = null;
            }else{
                pre = pre.next;
            }
                
        }
        return dummyHead.next;
        
    }

注意：这里返回时不能直接return head;

测试用例：

    public class ListNode {

    public int val;
    public ListNode next;

    public ListNode(int x) {
        val = x;
    }

    // 链表节点的构造函数
    // 使用arr为参数，创建一个链表，当前的ListNode为链表头结点
    public ListNode(int[] arr){

        if(arr == null || arr.length == 0)
            throw new IllegalArgumentException("arr can not be empty");

        this.val = arr[0];
        ListNode cur = this;
        for(int i = 1 ; i < arr.length ; i ++){
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
    }

    // 以当前节点为头结点的链表信息字符串
    @Override
    public String toString(){

        StringBuilder s = new StringBuilder();
        ListNode cur = this;
        while(cur != null){
            s.append(cur.val + "->");
            cur = cur.next;
        }
        s.append("NULL");
        return s.toString();
    }
}

递归解法

    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;
        }        
    }

参考：《玩转数据结构》

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

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

转载请注明本文地址：https://www.ucloud.cn/yun/77602.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：移除链表元素 Remove LinkedList Elements

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

makeFoxPlay 2019-07-31 11: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
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