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

链表与递归

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

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

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

这一节我们将从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;
    }

运行结果,成功通过。

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(4.1)Leetcode中和链表相关的问题

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多