资讯专栏INFORMATION COLUMN

链表与递归

alphahans / 694人阅读

摘要:链表与递归第题题目删除链表中等于给定值的所有节点。示例输入输出不使用虚拟头节点链表不为空,并且头节点就是要删除的元素所有元素都是要删除的元素,并且在上面已经删完现在的链表头节点不是要删除的元素删除不删除使用虚拟头节点虚拟头节点递归

链表与递归 LeetCode第203题
题目:
删除链表中等于给定值 val 的所有节点。
示例:

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

1.不使用虚拟头节点

public class Solution {

    public ListNode removeElements(ListNode head, int val) {

        // 链表不为空,并且头节点就是要删除的元素
        while (head != null && head.val == val) {
            ListNode delNode = head;
            head = head.next;
            delNode.next = null;
        }

        if (head == null) { 
            // 所有元素都是要删除的元素,并且在上面已经删完
            return head;
        } else { 
            // 现在的链表头节点不是要删除的元素
            ListNode prev = head;
            while (prev.next != null) {
                if (prev.next.val == val) { // 删除
                    ListNode delNode = prev.next;
                    prev.next = delNode.next;
                    delNode.next = null;
                } else { // 不删除
                    prev = prev.next;
                }
            }
            return head;
        }
    }
}

2.使用虚拟头节点

public class Solution2 {

    public ListNode removeElements(ListNode head, int val) {

        // 虚拟头节点
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode prev = dummyHead;
        while (prev.next != null) {

            if (prev.next.val == val) {
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            } else {
                prev = prev.next;
            }

        }
        return dummyHead.next;
    }
}

3.递归

public class Solution3 {

    public ListNode removeElements(ListNode head, int val) {

        if (head == null) {
            return head;
        }

        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;

    }

}

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

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

相关文章

  • 表与递归

    摘要:链表与递归第题题目删除链表中等于给定值的所有节点。示例输入输出不使用虚拟头节点链表不为空,并且头节点就是要删除的元素所有元素都是要删除的元素,并且在上面已经删完现在的链表头节点不是要删除的元素删除不删除使用虚拟头节点虚拟头节点递归 链表与递归 LeetCode第203题 题目: 删除链表中等于给定值 val 的所有节点。 示例: 输入: 1->2->6->3->4->5->6, v...

    lily_wang 评论0 收藏0
  • 【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-表与递归

    摘要:链表与递归已经从底层完整实现了一个单链表这样的数据结构,并且也依托链表这样的数据结构实现了栈和队列,在实现队列的时候对链表进行了一些改进。计算这个区间内的所有数字之和。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【从蛋壳到满天飞】JAVA 数据结构解析和算法实现,全部文...

    lastSeries 评论0 收藏0
  • 【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-表与递归

    摘要:链表与递归已经从底层完整实现了一个单链表这样的数据结构,并且也依托链表这样的数据结构实现了栈和队列,在实现队列的时候对链表进行了一些改进。计算这个区间内的所有数字之和。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【从蛋壳到满天飞】JAVA 数据结构解析和算法实现,全部文...

    alanoddsoff 评论0 收藏0
  • 双向表与LRU缓存淘汰机制

    摘要:双向链表双向链表作为在日常开发中最常用的数据结构之一,应用十分广泛,在诸多著名开源项目中如的结构,的中均是核心实现。 双向链表 双向链表作为在日常开发中最常用的数据结构之一,应用十分广泛,在诸多著名开源项目中如redis的list结构, groupcache的lru中均是核心实现。在设计此类数据集合的时候,外面看上去链表似乎与数组相似,但链表是一个非连续性内存的存储方案,提供了高效的节...

    nihao 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<