首页 > 编程语言 >有关链表算法题的一些思考

有关链表算法题的一些思考

时间:2024-03-30 18:31:00浏览次数:30  
标签:p3 p1 ListNode next 链表 算法 思考 null

1.针对链表的特性

(1)双指针的方法:因为不管是删除还是添加元素,都要涉及指定位置元素的上一个元素,因此需要设置前后两个指针来实现操作,同时针对题目特殊性也可能会有三指针的情况,如LeetCode82的去重,第一个指针作为删除操作的前一个指针,而后两个指针则用来查取重复范围

    /**
     *LeetCode 82
     * 删除重复元素
     */
    public ListNode deleteDuplicates(ListNode p) {
        //特殊链表
        if (p==null){
            return null;
        }
        ListNode s=new ListNode(-1,p);
        ListNode p1=s;
        ListNode p2;
        ListNode p3;

        while ((p2=p1.next)!=null&&(p3=p2.next)!=null){
            if (p2.val==p3.val){//元素的值相同
                while ((p3=p3.next)!=null&&p3.val==p2.val){
                }
                //此时的p3为值不重复的元素---删除值重复元素
                p1.next=p3;
            }else{//元素的值不同---三个指针同时后移
                p1=p1.next;
            }
        }
        return s.next;
    }

(2)递归:递归中可能存在多路递归的情况,是化多为少思想的应用,例如LeetCode23中,将合并多个链表的问题化简为二分递归和合并两个链表的情况,这种思想在解决数组内多个元素的处理时可能会用到

/**
 * 合并多个升序链表
 */
public ListNode mergeKLists(ListNode[] lists) {
        return spilt(lists, 0, lists.length - 1);
    }

    //采用二分的思想切割链表数组,化多为少,将数组切割为两两一组,然后合并后递归返回
    private ListNode spilt(ListNode[] lists, int i, int j) {
        if (lists.length == 0) {   //---------------bug
            return null;
        }
        if (i == j) {//---------------bug
            return lists[i];
        }
        int m = (i + j) >>> 1;//二分切割  //---------------bug
        ListNode left = spilt(lists, i, m);
        ListNode right = spilt(lists, m + 1, j);
        return mergeTwoLists(left, right);
    }

    private ListNode mergeTwoLists(ListNode p1, ListNode p2) {
        ListNode s = new ListNode(-1, null);//新链表的哨兵节点
        ListNode p3 = s;

        while (p2 != null && p1 != null) {
            if (p1.val < p2.val) {//将p1接到新链表
                p3.next = p1;
                p1 = p1.next;
                p3 = p3.next;
            } else {
                p3.next = p2;
                p2 = p2.next;
                p3 = p3.next;
            }
        }
        if (p1 == null) {
            p3.next = p2;
        } else {
            p3.next = p1;
        }
        return s.next;
    }

2.特殊链表的考虑

针对算法输入的特殊链表,因为算法中访问到next元素的val时可能出现next为null而报空指针异常的错误,常见处理为p!=null && p.next != null,前者是链表为空的情况,后者是针对边界特殊情况的处理

3.哨兵节点

由于头结点的特殊性,主体逻辑会在边界处出现bug,引入哨兵节点则是为了将边界节点的处理也纳入主体逻辑中

--具体使用情况可能由处理的链表决定,待考察...

标签:p3,p1,ListNode,next,链表,算法,思考,null
From: https://blog.csdn.net/fengdongnan/article/details/137178263

相关文章

  • COMP2017 9017 多类型链表数据结构
    COMP20179017课业2到期时间:2024年3月28日23:59这项任务相当于你最终评估的10%任务描述您的任务是创建一个多类型链表数据结构和与之交互的程序任务分为三个任务,必须按顺序完成。第一部分是链表的基本命令语法、创建、删除、查看等。第二部分是通过插入和删除元素来修改现有的列......
  • 四数之和算法讲解
    题目给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a],nums[b],nums[c],nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):0<=a,b,c,d <na、b、c 和 d 互不相同nums[a]+num......
  • 图解《程序员面试常见的十大算法》及代码实现
    关注我,持续分享逻辑思维&管理思维;可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导;有意找工作的同学,请参考博主的原创:《面试官心得--面试前应该如何准备》,《面试官心得--面试时如何进行自我介绍》, 《做好面试准备,迎接2024金三银四》。推荐热榜内容:《C#实例:SQL如何添加......
  • 时间序列预测算法python全集合--深度学习
    共整理了60+个深度学习的时间序列预测算法,Python代码,包括多输入单输出,单输入单输出。深度学习算法主要为:LSTM,bilstm,grubigru,arima,ssa-arima,ceemdan,bp,elm,kelm,knn,mlp,slp,svm,XGBOOST,lightgbm,catboost,rf,lssvm,RNN,SARIMA,transformer等智能优化算法:SSA,WOA,AVOA,CS,DBO,FA,FWA,GW......
  • Offer必备算法18_栈_五道力扣题详解(由易到难)
    目录①力扣1047.删除字符串中的所有相邻重复项解析代码②力扣844.比较含退格的字符串解析代码③力扣227.基本计算器II解析代码④力扣394.字符串解码解析代码⑤力扣946.验证栈序列解析代码本篇完。①力扣1047.删除字符串中的所有相邻重复项1047.删除字符......
  • Tarjan 算法——图论学习笔记
    Part.1引入在图论问题中,我们经常去研究一些连通性问题,比如:有向图的联通性:传递闭包——Floyd算法;有向图连通性的对称性:强联通分量(SCC)——Tarjan算法缩点;无向图的联通性:并查集;无向图的关键边:桥(割边)、边双——Tarjan算法缩点;无向图的关键点:割点、点双——Tarjan建立圆方......
  • 莫队算法学习笔记
    Part.1引入当你遇到一个区间询问但是难以用线段树等log算法维护的时候怎么办?那就是——莫队!莫队这个东西能支持区间修改、区间查询的操作,但是这种算法要求离线。莫队有很多种,详细请看下文。Part.2普通莫队我们先来看一道例题(P1972的削弱版):给你一个长度为\(n\)的序列......
  • 【力扣hot100】160.相交链表
    相交链表给你两个单链表的头节点headA和headB,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回null。图示两个链表在节点c1开始相交:题目数据保证整个链式结构中不存在环。注意,函数返回结果后,链表必须保持其原始结构。示例1:输......
  • KMP算法
    对于字符串“abababca”,它的next如下表所示:voidget_next(SStringT,int*next){inti=1,j=0;next[1]=0;//next[1]的值总是0while(i<T.length){if(j==0||T.ch[i]==T.ch[j]){//如果j处于0位或者,俩字符相等++i......
  • 基于DWT(离散小波变换)的图像加密水印算法,Matlab实现
           博主简介:专注、专一于Matlab图像处理学习、交流,matlab图像代码代做/项目合作可以联系(QQ:3249726188)       个人主页:Matlab_ImagePro-CSDN博客       原则:代码均由本人编写完成,非中介,提供有偿Matlab算法代码编程服务,不从事不违反涉及学术原则......