左程云老师算法课笔记（二）

前言

仅记录学习笔记，如有错误欢迎指正。
最近，有点忙，也有点懈怠，还是要加油加油，共勉。

二.链表

hashmap注意value为基本类型为引用传递，不copy一份，而非基本类型为值传递，会copy一份值到value里面！

如何使用快慢指针技巧来找寻单链表中点！

如何要判断一个链表是否回文

• 笔试写法：直接遍历链表入栈，然后出栈和遍历链表的值比较，全部相同返回true

• 面试思路：快慢指针到中点，上图1，然后右半部分反转链表，然后左边从左到右遍历，右边从右到左遍历，比较相同返回true；

题目：

如何找出一个链表是否有环，找出入环的第一个节点

• 笔试写法：一定想到hashset,第二次进入的就是入环节点

• 面试思路：快慢指针相遇后，快指针回到原点，慢指针不动，然后都一步一步走，他们一定会在入环节点相遇。

如何找出两个单链表的相交节点

（1）都无环：求出长链表减去短链表的长度为k，然后长链表先走k，之后长短链表一起走，二者相等为相交节点

（2）一个有环一个没环：不存在相交节点！

（3）都有环：

• （1）不交
• （2）不在环中相交：end节点选入环的节点，同（1），
• （3）在环中相交：判断loop1在环走能不能遇见loop2，可以就是为(3).3的情况，此时返回loop1或者loop2 的相交节点都对

getLoopNode 就是获取相交节点
第一个if走（1）
第二个走（3）