链表 OJ（一）

移除链表元素

题目连接：
https://leetcode.cn/problems/remove-linked-list-elements/description/

在这里插入图片描述

使用双指针法，开始时，一个指针指向头节点，另一个指针指向头节点的下一个结点，然后开始遍历链表删除结点。

这里要注意如果是空链表的话，使用双指针第二个指针会发生空指针异常，所以要判断一下

最后程序运行到最后，我们还差头节点没有判断，最后加上即可。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) {
            return head;
        }

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

        if(head.val == val) {
            head = head.next;
        }
        return head;
    }
}

反转链表

题目连接：
https://leetcode.cn/problems/reverse-linked-list/description/

在这里插入图片描述

我们还是使用双指针，不过这次有一个指针就是头指针，因为反转链表之后的头指针会发生改变，那还不如直接让头指针一起移动，先将另一个指针指向头指针的下一个结点，然后开始遍历链表，把每一个结点的指针指向的对象变为前面的对象。

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) {
            return head;
        }
        
        ListNode cur = head.next;
        head.next = null;

        while(cur != null) {
            ListNode tmp = cur.next;
            cur.next = head;
            head = cur;
            cur = tmp;
        }
        
        return head;
    }
}

链表的中间结点

题目链接：
https://leetcode.cn/problems/middle-of-the-linked-list/description/

在这里插入图片描述

使用快慢指针，快指针每次走两步，慢指针每次走一步，最后慢指针所指向的结点就是 中间结点

原理：fast = 2slow = 总路程

这里要注意循环的结束条件：
在这里插入图片描述当fast== null 并且 fast.next == null时，才能进入循环，并且 fast==null,要放在前面，因为只用fast不是null时才能进行 fast.next 的判断

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }
}

返回倒数第 k 个节点

题目链接：
https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/

在这里插入图片描述

还是使用快慢指针，先让快指针走 k-1 步，然后慢指针和快指针一起走，每次走一步，最后快指针走到最后一个结点时，慢指针所指向的节点就是倒数第 k 个节点。

原理就是让slow和fast的差值j就是k

class Solution {
    public int kthToLast(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;

        for(int i=0; i<k-1; i++) {
            fast = fast.next;
        }

        while(fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow.val;
    }
}

合并两个有序的链表

题目链接：
https://leetcode.cn/problems/merge-two-sorted-lists/description/
在这里插入图片描述

创建一个新的头节点，list1和list2开始遍历各自的链表，然后比较，插入到新链表中，最后再看一下哪些链表没有遍历完，然后把没有遍历完的链表直接插入即可。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }

        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        
        if(list1 != null) {
            cur.next = list1;
        }
        if(list2 != null) {
            cur.next = list2;
        }

        return newHead.next;
    }
}

分割链表

题目链接：
https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

在这里插入图片描述

我们可以将单链表拆成两个链表，一个链表存储小于x 的结点，另一个链表存储大于等于x 的结点，然后将两个链表合并

这里建议使用带头链表，也就是我们常说的带哨兵位的链表，这个链表最大的好处就是可以避免头插的复杂情况，既然使用了哨兵位，就要知道最后哨兵位是要被丢弃的。

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        ListNode headA = new ListNode(-1);
        ListNode aLast = headA;
        ListNode headB =  new ListNode(-1);
        ListNode bLast = headB;

        ListNode cur = pHead;
        while(cur != null) {
            if(cur.val < x) {
                aLast.next = cur;
                aLast = aLast.next;
            } else {
                bLast.next = cur;
                bLast = bLast.next;
            }
            cur = cur.next;
        }

        aLast.next = headB.next;
        bLast.next = null;
        return headA.next;
    }
}

链表的回文结构

题目链接：
https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
在这里插入图片描述

解题思路：
我们可以使用快慢指针来遍历链表找到中间结点，然后就可以把后半部分的链表进行反转，之后从这个链表头尾结点开始向中间遍历。

易错点：
1.链表的结点个数有奇数和偶数两种类型，我们需要分别讨论
2.区分奇数个结点还是偶数个结点可以从一开始找完中间结点的时候，从fast入手,因为找中间结点的循环结束就是fast最后指向尾节点还是null。
3.要一定要保存好fast的信息，因为后面在反转链表的时候fast其实已经发生了改变。

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        //如果是空链表返回true
        if(A == null) {
            return true;
        }

        ListNode slow = A;
        ListNode fast = A;

        //找到中间结点
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //保存fast的结点信息，避免后面反转链表丢失信息
        boolean isOdd = true;//是否是奇数个结点
        if(fast == null) {
            isOdd = false;
        }

        //反转后半部分的链表
        ListNode prev = slow;
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curN = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curN;
        }

        //前后遍历链表
        ListNode pA = A;
        ListNode last = prev;

        //偶数个结点
        if(!isOdd) {
            while(pA.next != last) {
                if(pA.val != last.val) {
                    return false;
                }
                pA = pA.next;
                last = last.next;
            }
            if(pA.val != last.val) {
                return false;
            }
        }
        if (isOdd) { //奇数个结点
            while(pA != last) {
                if(pA.val != last.val) {
                    return false;
                }
                pA = pA.next;
                last = last.next;
            }
        }

        return true;
    }
}

相交链表

题目链接：
https://leetcode.cn/problems/intersection-of-two-linked-lists/

在这里插入图片描述

由于是相交链表，在公共结点之前两个链表可能有一个差值，如果我们能找到这个差值，让长的链表先走差值不属，然后两个链表一起遍历，直到相遇到公共结点。

这个差值就是两个链表的长度的差。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;

        ListNode cur = headA;
        while(cur != null) {
            lenA++;
            cur = cur.next;
        }
        
        cur = headB;
        while(cur != null) {
            lenB++;
            cur = cur.next;
        }

        int k = 0;
        ListNode pl = null;
        ListNode ps = null;
        if(lenA > lenB) {
            k = lenA - lenB;
            pl = headA;
            ps = headB;
        } else {
            k = lenB - lenA;
            pl = headB;
            ps = headA;
        }

        while(k != 0) {
            pl = pl.next;
            k--;
        }

        while(pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }

        return pl;
    }
}

环形链表

题目链接：
https://leetcode.cn/problems/linked-list-cycle/

在这里插入图片描述

这里使用快慢指针，快指针一次走两步，慢指针一次走一步，当快指针运动到fast == null 或者 fast .next == null 这个条件时，说明链表不存在环，如果有链表存在环，那么快指针就会先进入到环中一直做圆周运动，一定会存在某一个时刻快慢指针会相遇，这时候返回true即可。

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        } 

        return false;
    }
}

为什么快指针每次走两步，慢指针走一步可以？

快指针会率先进入环中，然后慢指针后晚一点进入环中，由于两个指针的速度是每次差一步，也就是说两个指针每运动一次，二者之间的距离就会缩短1步，最后两个指针一定会相遇。

快指针一次走3步，走4步，…n步行吗？
快指针如果每次走三步，假设两个指针的位置如下：
在这里插入图片描述
那二者永远都不会相遇

其他情况由读者自行探讨~~

环形链表Ⅱ （找入口点）

题目链接：
https://leetcode.cn/problems/linked-list-cycle-ii/description/

在这里插入图片描述

我们还是使用快慢指针来做。

假设起点与入口点的距离为 x ，环的周长为 C ，慢指针与快指针相遇点离起点的距离为L ：
在这里插入图片描述
慢指针所走的路程为 x + L
快指针所走的路程为 x + L + nC (n为正整数，n = 1,2,3,4…)

这里解释一下两者的路程计算问题：
在慢指针还没有进入口点的时候，就已经至少路过一次相遇点，所以当慢指针刚刚进入环中的时候，快指针最少已经走了一圈，最多走了 n 圈。
因为慢指针刚进入环中的时候，快指针和它最多相差一个圈的距离，并且快指针的速度比慢指针的速度要快，所以慢指针是不可能走完一圈的（假设慢指针走完一圈，那快指针一定走完一圈再多一点，所以慢指针在完成一圈之前一定会被追上），所以慢指针所走的路程为 x + L，快指针所走的路程为 x + L + nC (n为正整数，n = 1,2,3,4…)中的 nC 是遇到慢指针之前就已经完成好的

当快慢指针在环中相遇时，由于快指针的速度是慢指针的速度的两倍，所以慢指针的路程是快指针的一半，即 2 * (x + L) = x + L + nC，化简整理得 x + L = nC 即 x = nC - L

推导结论：
让一个指针从头开始遍历，另一个指针从相遇点开始遍历，两个指针每次走一步，一定会在入口点相遇。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                break;
            }
        }

        //没有环
        if(fast == null || fast.next == null) {
            return null;
        }

        ListNode meet = fast;
        ListNode str = head;

        while(meet != str) {
            meet = meet.next;
            str = str.next;
        }
        
        return str;
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/791074.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

YOLOv10改进 | Conv篇 | CVPR2024最新DynamicConv替换下采样（解决低FLOPs陷阱）

YOLOv10改进 | Conv篇 | CVPR2024最新DynamicConv替换下采样（解决低FLOPs陷阱）

一、本文介绍 本文给大家带来的改进机制是CVPR2024的最新改进机制DynamicConv其是CVPR2024的最新改进机制&#xff0c;这个论文中介绍了一个名为ParameterNet的新型设计原则&#xff0c;它旨在在大规模视觉预训练模型中增加参数数量&#xff0c;同时尽量不增加浮点运算&#x…
阅读更多...
YOLOv10改进 | Conv篇 | 全新的SOATA轻量化下采样操作ADown（参数量下降百分之二十，附手撕结构图）

YOLOv10改进 | Conv篇 | 全新的SOATA轻量化下采样操作ADown（参数量下降百分之二十，附手撕结构图）

一、本文介绍 本文给大家带来的改进机制是利用2024/02/21号最新发布的YOLOv9其中提出的ADown模块来改进我们的Conv模块&#xff0c;其中YOLOv9针对于这个模块并没有介绍&#xff0c;只是在其项目文件中用到了&#xff0c;我将其整理出来用于我们的YOLOv10的项目&#xff0c;经…
阅读更多...
Python 视频的色彩转换

Python 视频的色彩转换

这篇教学会介绍使用OpenCV 的cvtcolor() 方法&#xff0c;将视频的色彩模型从RGB 转换为灰阶、HLS、HSV...等。 因为程式中的OpenCV 会需要使用镜头或GPU&#xff0c;所以请使用本机环境( 参考&#xff1a;使用Python 虚拟环境) 或使用Anaconda Jupyter 进行实作( 参考&#x…
阅读更多...
【TAROT学习日记】韦特体系塔罗牌学习（1）——愚者 THE FOOL 0

【TAROT学习日记】韦特体系塔罗牌学习（1）——愚者 THE FOOL 0

韦特体系塔罗牌学习&#xff08;1&#xff09;——愚者 THE FOOL 0 https://www.tarotchina.net/major-arcana0-vip/ 目录 韦特体系塔罗牌学习&#xff08;1&#xff09;——愚者 THE FOOL 0牌面分析1. 基础信息2. 图片元素 正位牌意1. 关键词/句2.爱情婚姻3. 学业事业4. 人际关…
阅读更多...
android13 rom frameworks 蓝牙自动接收文件

android13 rom frameworks 蓝牙自动接收文件

总纲 android13 rom 开发总纲说明 目录 1.前言 2.源码查找 3.我们先实现第一种改法 4.实现第二种改法 5.第三种改法代码参考 6.编译测试 1.前言 我们从导航栏这里，点开这个蓝牙的接收框，弹出来的对话框，使用android studio 的layout inspector可以发现这个是 Bluetoo…
阅读更多...
有必要找第三方软件测评公司吗?如何选择靠谱软件测评机构?

有必要找第三方软件测评公司吗?如何选择靠谱软件测评机构?

软件测试是确保软件质量的重要环节&#xff0c;而在进行软件测试时&#xff0c;是否有必要找第三方软件测评公司呢?第三方软件测评公司是指独立于软件开发公司和用户之间的中立机构&#xff0c;专门从事软件测试和测评工作。与自身开发团队或内部测试团队相比&#xff0c;选择…
阅读更多...
大白话讲解AI大模型

大白话讲解AI大模型

大白话讲解大模型 大模型的发展重要大模型发展时间线 大模型的简单原理-训练⼤模型是如何训练并应⽤到场景中的&#xff1f;如果训练私有化模型 模型&#xff1a;model 语料库&#xff1a;用于训练模型的数据 大模型的发展 详细信息来源&#xff1a;DataLearner 2022年11月底…
阅读更多...
JVM相关知识点汇总

JVM相关知识点汇总

JDK，JRE以及JVM的关系 我们的编译器到底干了什么事？ 仅仅是将我们的 .java 文件转换成了 .class 文件，实际上就是文件格式的转换，对等信息转换。 类加载机制是什么？ > **所谓类加载机制就是** > ``` > 虚拟机把Class文件加载到内存 > 并对数据进行校验，转换…
阅读更多...
web安全及内网安全知识

web安全及内网安全知识

本文来源无问社区&#xff08;wwlib.cn&#xff09;更多详细内容可前往观看http://www.wwlib.cn/index.php/artread/artid/7506.html Web安全 1、sql注入 Web程序中对于用户提交的参数未做过滤直接拼接到SQL语句中执行&#xff0c;导致参数中的特殊字符破坏了SQL语句原有逻…
阅读更多...
qt 用数据画一个图，并表示出来

qt 用数据画一个图，并表示出来

1.概要 想用数据绘制一个画面&#xff0c;看有相机到播放的本质是啥。 要点 // 创建一个QImage对象&#xff0c;指定图像的宽度、高度和格式 QImage image(width, height, QImage::Format_Grayscale8); // 将像素数据复制到QImage对象中 memcpy(image.bits(), pixelD…
阅读更多...
【Linux网络】IP协议{初识/报头/分片/网段划分/子网掩码/私网公网IP/认识网络世界/路由表}

【Linux网络】IP协议{初识/报头/分片/网段划分/子网掩码/私网公网IP/认识网络世界/路由表}

文章目录 1.入门了解2.认识报头3.认识网段4.路由跳转相关指令路由 该文诸多理解参考文章&#xff1a;好文&#xff01; 1.入门了解 用户需求&#xff1a;将我的数据可靠的跨网络从A主机送到B主机 传输层TCP&#xff1a;由各种方法&#xff08;流量控制/超时重传/滑动窗口/拥塞…
阅读更多...
PTC可复位保险丝 vs 传统型保险丝：全面对比分析

PTC可复位保险丝 vs 传统型保险丝：全面对比分析

PTC可复位保险丝&#xff0c;又称为自恢复保险丝、自恢复熔断器或PPTC保险丝&#xff0c;是一种电子保护器件。它利用材料的正温度系数效应&#xff0c;即电阻值随温度升高而显著增加的特性&#xff0c;来实现电路保护。 当电路正常工作时&#xff0c;PTC保险丝呈现低阻态&…
阅读更多...
最新浪子授权系统网站源码 全开源免授权版本

最新浪子授权系统网站源码 全开源免授权版本

最新浪子授权系统网站源码 全开源免授权版本 此版本没有任何授权我已经去除授权&#xff0c;随意二开无任何加密。 更新日志 1.修复不能下载 2.修复不能更新 3.修复不能删除用户 4.修复不能删除授权 5.增加代理后台管理 6.重写授权读取文件 7.修复已经知道漏洞 源码下…
阅读更多...
2-30 基于matlab的神经网路下身份证号码识别算法

2-30 基于matlab的神经网路下身份证号码识别算法

基于matlab的神经网路下身份证号码识别算法&#xff0c;二值化、膨胀处理、边界区域划分、身份证字符分割&#xff0c;字符识别算法&#xff0c;输出识别结果。并保存识别结果。程序已调通&#xff0c;可直接运行。 2-30 神经网络 身份证识别 图像处理 - 小红书 (xiaohongshu.c…
阅读更多...
jdk中自带的并发类

jdk中自带的并发类

1、seamplore 信号量 countDownLaunch&#xff1a;等待所有线程都完成&#xff0c;主线程在执行 CyclicBarrirer 内存屏障 exchanger 线程之间交换数据 phaser 阶段协同器 阻塞队列
阅读更多...
【高中数学/对数函数】比较a=ln2/2,b=ln5/5的大小

【高中数学/对数函数】比较a=ln2/2,b=ln5/5的大小

【问题】 比较aln2/2,bln5/5的大小 【解答】 a-bln2/2-ln5/5(5*ln2-2*ln5)/10(ln2^5-ln5^2)/10(ln32-ln25)/10>0 所以a>b 【图像】 如果绘出函数ylnx/x的图像&#xff0c;再标记出a,b的位置&#xff0c;则绘出图像如下&#xff1a; 由上图可以看出&#xff0c;a,b两…
阅读更多...
数据库数据恢复—SQL Server数据库由于存放空间不足报错的数据恢复案例

数据库数据恢复—SQL Server数据库由于存放空间不足报错的数据恢复案例

SQL Server数据库数据恢复环境&#xff1a; 某品牌服务器存储中有两组raid5磁盘阵列。操作系统层面跑着SQL Server数据库&#xff0c;SQL Server数据库存放在D盘分区中。 SQL Server数据库故障&#xff1a; 存放SQL Server数据库的D盘分区容量不足&#xff0c;管理员在E盘中生…
阅读更多...
2025最新付费进群系统源码 修复版

2025最新付费进群系统源码 修复版

2025最新付费进群系统 修复一堆bug 修复分销无法添加 易支付只能在文件里更改等等问题 源码下载&#xff1a;https://download.csdn.net/download/m0_66047725/89515782 更多资源下载&#xff1a;关注我。
阅读更多...
Qt基础控件总结—多页面切换(QStackWidget类、QTabBar类和QTabWidget类)

Qt基础控件总结—多页面切换(QStackWidget类、QTabBar类和QTabWidget类)

QStackedWidget 类 QStackedWidget 类是在 QStackedLayout 之上构造的一个便利的部件，其使用方法与步骤和 QStackedLayout 是一样的。QStackedWidget 类的成员函数与 QStackedLayout 类也基本上是一致的，使用该类就和使用 QStackedLayout 一样。 使用该类可以参考QStackedL…
阅读更多...
初阶数据结构—排序

初阶数据结构—排序

第一章&#xff1a;排序的概念及其运用 1.1 排序的概念 排序&#xff1a;所谓排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作。 稳定性&#xff1a;假定在待排序的记录序列中&#xff0c;存在多个具有…
阅读更多...
最新文章

Copyright @ 2022~2023