• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(4.1)Leetcode中和链表相关的问题

极客笔记 Geekerstar 11个月前 (05-13) 287次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

链表与递归

上一章我们从底层完整的实现了链表这一数据结构,并且基于此实现了栈和队列两种数据结构,并作出了一些改进。

这一节我们将深入研究递归,可能有些同学觉得递归这个话题总是和数连接在一起的。

事实的确如此,不过可能有很多同学忽略了一点,在链表这种结构上,也是可以使用递归这种方法的,因为链表本身就天然的具有递归性质。

这一节我们将从LeetCode中的链表相关的题目来作为切入点。

203. 删除链表中的节点

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

示例:

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

本题还给了我们解题模板,我们需要按照此格式来编写代码。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        
    }
}

答案1-不使用虚拟头结点

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;

        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-使用虚拟头结点

class Solution {

    public ListNode removeElements(ListNode head, int val) {

        while(head != null && head.val == val)
            head = head.next;

        if(head == null)
            return head;

        ListNode prev = head;
        while(prev.next != null){
            if(prev.next.val == val)
                prev.next = prev.next.next;
            else
                prev = prev.next;
        }

        return head;
    }

运行结果,成功通过。

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(4.1)Leetcode中和链表相关的问题
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00