【Java数据结构】经典链表OJ题——超详细做题笔记及心得

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

【Java数据结构】经典链表OJ题——超详细做题笔记及心得(每行代码都有注释嗷)

⭐1.反转链表

⭐2.给定一个带有头结点 head 的非空单链表,返回链表的中间结点

⭐3.输入一个链表输出该链表中倒数第K个节点

⭐4.将两个有序链表合并为一个新的有序链表并返回

⭐5.分割链表

⭐6.删除链表中重复节点(重复节点不保留)

⭐7.判断链表是否是回文结构

⭐8.找出两个链表的第一个公共节点

⭐9.判断链表是否有环

⭐10.返回链表开始入环的第一个节点

⭐1.反转链表

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

要实现上图的效果,需要以下步骤:

①设置两个指针,cur 指向链表头节点,prev 指向空

②暂存 cur 的后继节点,curNext = cur.next

③将 cur.next 反指向prev(一开始prev为空)

④prev 指针后移,即将 prev 指向 cur

⑤cur 指针后移 ,即将 cur 指向 2 中暂存的 curNext 节点

⑥循环: 第2 到 5 步,直到 cur 遍历完整个链表

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

⭐2.给定一个带有头结点 head 的非空单链表,返回链表的中间结点



【Java数据结构】经典链表OJ题——超详细做题笔记及心得



【Java数据结构】经典链表OJ题——超详细做题笔记及心得

解题思路:

本题用的是双指针的方法
①分别设置一个快指针和一个慢指针
②快指针每次走两步,慢指针每次走一步
③当快指针走到最后尾节点的时候,慢指针就走到了链表中间节点

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

⭐3.输入一个链表输出该链表中倒数第K个节点


【Java数据结构】经典链表OJ题——超详细做题笔记及心得

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

具体需要以下步骤:

①初始化: 前指针 former 、后指针 latter ,双指针都指向头节点 head 。

②构建双指针距离: 前指针 former 先向前走 k-1 步(结束后,双指针 former 和 latter 间相距 k-1步)。

③双指针共同移动: 循环中,双指针 former 和 latter 每轮都向前走一步,直至 former 走到链表 尾节点 时跳出(跳出后, latter 与尾节点距离为 k-1步,即 latter 指向倒数第 k 个节点)

④返回值: 返回 latter 即可。


【Java数据结构】经典链表OJ题——超详细做题笔记及心得

⭐4.将两个有序链表合并为一个新的有序链表并返回

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

具体步骤如下
①设置傀儡节点,傀儡节点后边的节点组成的链表就是合并后的链表
②比较两个链表的每个节点,存入傀儡节点后的合并链表
③当有一条链已经遍历完成则将另一条链接到合并链表的尾部
④最后返回的是傀儡节点的下一个节点,这才是合并后的链表的头结点

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

⭐5.分割链表

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

⭐6.删除链表中重复节点(重复节点不保留)

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

解题思路:

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

⭐7.判断链表是否是回文结构

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

⭐8.找出两个链表的第一个公共节点

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

解题思路:这里说一种很6P的解法,是leetcode上看到的一个题解

直接将两条路分别拼接在对方末尾,这样两条路便一样长,再从这两条新的路起始点往后比较即可,如下图 节点相同地方一句圈起来,两条链表记住,公共节点指的就是公用一个节点,不是值相同,所以要对比的是地址,蓝色连接代表链表结束换路

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

⭐9.判断链表是否有环

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

⭐10.返回链表开始入环的第一个节点

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

解题思路:

我们使用两个指针,fast 与 slow。它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置,而fast 指针向后移动两个位置。如果链表中存在环,则 fast 指针最终将再次与 slow 指针在环中相遇

如下图所示,设链表中环外部分的长度为 a。slow 指针进入环后,又走了 b 的距离与 fast 相遇。此时,fast 指针已经走完了环的 n 圈,因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc

【Java数据结构】经典链表OJ题——超详细做题笔记及心得

根据题意,任意时刻,fast 指针走过的距离都为slow 指针的 2 倍。因此,我们有

a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

有了 a=c+(n-1)(b+c)的等量关系,我们会发现:从相遇点到入环点的距离加上 n-1圈的环长,恰好等于从链表头部到入环点的距离。

因此,当发现 slow 与 fast 相遇时,我们再额外使用一个指针 tmp它指向链表头部;随后,它和 slow 每次向后移动一个位置。最终,它们会在入环点相遇。

解题步骤:

①利用快慢指针方法找相遇点

②找到相遇点之后,设置临时变量tmp代替头结点,tmp和slow同时移动,直至相遇

③相遇点即为环的呃入口


【Java数据结构】经典链表OJ题——超详细做题笔记及心得


上一篇:Schedulerx2.0分布式计算原理&最佳实践


下一篇:Akka in Schedulerx2.0