8. 相交链表
160. 相交链表 - 力扣（Leetcode）
8.1 代码实现
节点类型跟之前的一样~
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode curA = headA; ListNode curB = headB; while(curA != null && curB != null) { curA = curA.next; curB = curB.next; } while(curA != null) { headA = headA.next; curA = curA.next; } while(curB != null) { headB = headB.next; curB = curB.next; } while(true) { if(headA == headB) { return headA; } headA = headA.next; headB = headB.next; } } }
8.2 深度解析 + 动图分析
一开始想到的方法就是，遍历N2次， 即一个链表，每一个节点都在另一条链表上（整趟）找
很笨~
相交单链表的特点就是，交点到链尾，两个表是完全重合的，也就是说，两条相交的单链表，个数上的差异取决于节点之前的个数差异~
当然也可以用两次遍历确认两条的长度，然后让他们前半段的个数差抵消~
但是我不喜欢多遍历一次去测长度~
且看看我的方法~
是相交链表：
不是相交链表：
这样都指向null的时候，就会返回null
不相交返回空~
9. 循环链表之判断是否带环
141. 环形链表 - 力扣（Leetcode）
9.1 代码实现
节点类型跟之前的一样~
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; } }
9.2 深度解析 + 动图分析
这里结合了 “快慢指针” 的性质
让两个指针速度不一样，当进入循环链表的时候
由于速度不一样，两个指针会相遇~
如果不是循环链表，快指针会很快指向null~
为什么“快慢指针”的速度为2:1？
因为其他比例，例如3:1 ，可能会导致循环链表，两个引用一直没相遇，反复错过，绕多了很多圈~
如果结尾出现，两个节点的循环，并且slow在前，fast在后~
就会出现死循环~
对于第十问，2:1 有很大的帮助！
10. 循环链表之入口点
142. 环形链表 II - 力扣（Leetcode）
10.1 代码实现
节点类型跟前面一模一样~
public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head; ListNode cur = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { while(cur != slow) { cur = cur.next; slow = slow.next; } return slow; } } return null; } }
10.2 深度解析 + 动图分析
只需要在第九题的基础上，做一些更改~
作为返回值，如果不是循环链表返回null
如果是循环链表，返回入口点，那么入口点的计算算法是什么呢？
在第九题的基础上，我们找到了相遇点，而相遇点不一定是入口点~
所以两个指针必须同时走，一快一慢~
对于相遇点有这么一个性质：相遇点与链表头节点，两个引用这两个点出发，速度为1的情况下，会在入口点相遇~
下面看我证明：
得到这个结论，因为我是按单位长度来算的，所以，只要是循环链表，就满足这个公式~
无非就是有些量为0的特殊情况~
这也是为什么用两倍的关系，这样才有这么好的性质~
这就是这一段代码的由来~
差不多就这样：
11. 补充知识点~
LinkedList有一个和顺序表一样的构造方法，可以提供一个集合类，完成拷贝~
链表知识点题库 - 力扣（LeetCode）
牛客网在线编程_编程学习|练习题_数据结构|系统设计题库 (nowcoder.com)
学会自主学习~
你现在有能力刷题了哦~
11.1 LinkedList链表的反向遍历~
对于单链表，逆序打印开销实在太大了~
所以可以借助迭代器（了解）
ListIterator是List受重写后的一个方法，listIterator(int index)
index为迭代器内部的引用，指向的是index下标~
这个迭代器既可以顺序打印，也可以逆序打印~
逆序的话，用listIterator.hasPrevious()为条件，内置引用前有元素，即可打印
listIterator.previous()为内置引用的元素
并且调用一次，引用往前走一步
public static void main(String[] args) { List<Integer> list = new LinkedList<>(); list.add(55); list.add(56); list.add(57); list.add(58); list.add(59); ListIterator<Integer> listIterator = list.listIterator(list.size()); while(listIterator.hasPrevious()) { System.out.print(listIterator.previous() + " "); } }
结果正常~
11.2 ArrayList 与 LinkedList的区别
不同点 ArrayList LinkedList
存储空间 空间分布紧密连续 逻辑上连续，但是空间分布分散
随机访问 O(1) O(N)
头插 需要挪动元素，O( N ) O(1)
插入 空间不够需扩容 无容量概念
应用场景 元素高效存储 + 访问次数多 频繁插入，频繁删除
11.3 链表归并排序（知识扩展）【涉及排序原理】
时间复杂度O(N * log2N), 空间复杂度O( 1 )；
思路跟刚才归并怎么排一致，重点在于用快慢指针找到中点，节省速度
是可以先求长度然后一直用的（就是算一次长度，然后每次都用这个长度为基准，去找mid）
之后不断合并有序链表。
看几次动图：
递归的重点就分清“整体感”，比如说下面的，我们就看做左右边已经弄好了，只要满足小问题（递归出口
），通过数学归纳法就能知道成立
ListNode left = sortList(head); ListNode right = sortList(tmp);
public ListNode sortList(ListNode head) { if(head == null || head.next == null) { return head; } ListNode slow = head; ListNode fast = head.next; //避免当剩余两个节点时，中间节点变成右边那个，这样会死递归！ //（打断链表更没有意义，右边链表是null，没用） while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } ListNode tmp = slow.next; slow.next = null; //打断链表
技巧1：平分链表（快慢指针在Java中应该是引用，或者下标）
快慢指针，慢指针应该走到中间偏前的一个位置【不然会死递归】
以两个节点为例子，快指针走两步，慢指针走一步，然后slow.next = null不就等于没有意义吗， 进入递归后，（左侧）依旧是两个节点，以此造成栈溢出！
解决方法：fast先走一步，最终slow停在中节点偏前
fast不先走一步，最终slow停在中节点偏后
ListNode left = sortList(head); ListNode right = sortList(tmp); ListNode ret = new ListNode(0); //临时头节点，最终不要即可，因为我们不能确定头结点是否是谁的 ListNode cur = ret; while(left != null && right != null) { if(left.val <= right.val) { cur.next = left; left = left.next; }else { cur.next = right; right = right.next; } cur = cur.next; } cur.next = left != null ? left : right; return ret.next; }
技巧2： 给需要构造的链表提供一个起始节点，（就像珍珠需要有一个小石子，最终才能积累成珠）
ListNode ret = new ListNode(0);这一句代码，提供一个带头链表
目的是因为，我们不知道首节点是谁，毕竟尾入法在首节点需要判断
那我们不如直接给一个，最终不考虑进去就行了
技巧3：合并有序链表，不用多说
