个人认为链表这部分的算法相对简单，笔试中需要ac，面试需要能说明白为什么这么操作能保证其结果正确性就好了。
链表问题考察的时间复杂度，空间复杂度稍不重要，笔试中为了过怎么都可以，面试一定要聊时间空间都最优的解法，
环形链表
法一，用set将每个节点装进去，如果下次遇到同样地址的节点，那就代表有环，如果直到遍历的指针都为空了，还没有遇到重复的节点，那就是没有环了。注意set装的是节点的地址不是节点的值，值可以重复，但是地址值是唯一的。
法二，使用双指针，slow一次一步，fast 一次两步，如果fast遇到了null，那就是没有环。
如果fast == slow 了，那就是代表他们在环里相遇了，也就是存在环。
快慢指针正确性证明
让你求个证明，总不能来个显然成立吧？（狗头
假设该链表在环出现之前有L个结点，环中有C个结点。
再假设慢指针初始化时指向的位置为a、快指针初始化时指向的位置为b,
如果二者在 t 次移动后相遇，也就是说:
(a+t-L) mod C == (b + 2 * - L ) mod C,
所以无论a、b的起始位置如何，二者总是会相遇的。
推导:
( a + t - L ) mod C == (b+2 * t-L) mod C
a+t-L-m * C == b+2 * t-L -n * C
t == (a-b) - (m - n ) * C
a=b==> t == ( n - m ) * C;
在保证m和n为正整数的情况下，上式t有正整数解。
若两个指针的步长分别为: x和y (即每走一步步长分别为: x * t 和 y * t )
( x - y ) * t== (a-b)- (m-n)*C
要是程序不陷入死循环必须满足.上面这个等式有正整数解。
比方说:假设链表是由4个结点首尾相接构成的一个圆圈(编号为0~3)
慢指针初始位置在0，每次前进1步;
快指针初始位置在3，每次前进3步;
有: (3-1) *t==(3-0)- (m-n) *4
此等式没有正整数解，所以虽然这两个指针也是- -快- -慢一前一后，但它们永远也不会相
遇!
若快慢都在 0位置，
则有(0-0) *t==(0-0)- (m-n) *4
此时，是有整数解的，所以验证是否有环与快慢指针的初始位置有关，与快慢指针之间相差几步是没有关系的，总能找到一个对应的整数，使得其成立。
验证代码：
假设现在是
链表为 1-2-3-4-5-6 6->3 存在一个环
慢指针一次一步，快指针一次三步，初始位置都在head位置
public static boolean hasCycleTestByTwo( ListNode head ) {
if ( head == null || head.next == null ) {
return false;
}
ListNode slow = head;
ListNode fast = head;
int slowNum = 0;
int fastNum = 0;
while ( fast.next != null && fast.next.next != null ) {
System.out.println( "未相遇：slow.val=" + slow.val + " fast.val=" + fast.val );
slow = slow.next;
slowNum++;
fast = fast.next.next;
fastNum += 2;
if ( slow == fast ) {
System.out.println( "slow.val=" + slow.val + " fast.val=" + fast.val );
System.out.println( slowNum + " " + fastNum );
return true;
}
}
return false;
}
public static boolean hasCycleTestByThree( ListNode head ) {
if ( head == null || head.next == null ) {
return false;
}
ListNode slow = head;
ListNode fast = head;
int slowNum = 0;
int fastNum = 0;
while ( fast.next != null && fast.next.next != null && fast.next.next.next != null ) {
System.out.println( "未相遇：slow.val=" + slow.val + " fast.val=" + fast.val );
slow = slow.next;
slowNum++;
fast = fast.next.next.next;
fastNum += 3;
if ( slow == fast ) {
System.out.println( "slow.val=" + slow.val + " fast.val=" + fast.val );
System.out.println( slowNum + " " + fastNum );
return true;
}
}
return false;
}
public static void main( String[] args ) {
ListNode node1 = new ListNode( 1 );
ListNode node2 = new ListNode( 2 );
ListNode node3 = new ListNode( 3 );
ListNode node4 = new ListNode( 4 );
ListNode node5 = new ListNode( 5 );
ListNode node6 = new ListNode( 6 );
ListNode node7 = new ListNode( 7 );
ListNode node8 = new ListNode( 8 );
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node7;
node7.next = node8;
node8.next = node6;
System.out.println( "此时环入口为 " + node6.val + "号节点" );
System.out.println( hasCycleTestByTwo( node1 ) );
System.out.println( "此时环入口为 " + node6.val + "号节点" );
System.out.println( hasCycleTestByThree( node1 ) );
}
输出如下：
此时环入口为 6号节点
未相遇：slow.val=1 fast.val=1
未相遇：slow.val=2 fast.val=3
未相遇：slow.val=3 fast.val=5
未相遇：slow.val=4 fast.val=7
未相遇：slow.val=5 fast.val=6
未相遇：slow.val=6 fast.val=8
slow.val=7 fast.val=7
6 12
true
此时环入口为 6号节点
未相遇：slow.val=1 fast.val=1
未相遇：slow.val=2 fast.val=4
未相遇：slow.val=3 fast.val=7
未相遇：slow.val=4 fast.val=7
未相遇：slow.val=5 fast.val=7
未相遇：slow.val=6 fast.val=7
slow.val=7 fast.val=7
6 18
true
也可以ac
原题代码：
public boolean hasCycle(ListNode head) {
if(head==null || head.next==null) return false;
ListNode slow = head;
ListNode fast = head;
while ( fast.next!=null && fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
if(slow==fast)return true;
}
return false;
}
环形链表 II
法一，同上，先set判断，然后记录重复的节点，然后再从头遍历找到这个节点返回
法二，快慢指针，slow一次一步，fast一次两步，
快慢指针正确性证明
图源见水印
L=N*C-X
也就是说，head与相遇点的指针同时向后移动，相遇时，就是环的入口。
代码：
public ListNode detectCycle(ListNode head) {
if ( head==null || head.next==null)return null;
ListNode slow = head;
ListNode fast = head;
ListNode node = null;
while ( fast.next!=null && fast.next.next!=null ){
slow=slow.next;
fast=fast.next.next;
if(slow==fast){
node = slow;
break;
}
}
if(node != null){
ListNode temp = head;
while ( temp!=node ){
temp=temp.next;
node=node.next;
}
return temp;
}
return null;
}
回文链表
法一： 遍历节点全部放数组，然后判断
法二： 快慢指针找到中点，慢指针遍历过程中将节点压栈，将剩余的一半与栈顶元素依次比较，如果不想等返回false，直到栈空都没问题返回true
法三： 快慢指针找到中点，然后将中点之后的元素逆置，中点的next指向null，然后head 与 逆置部分后的头节点依次比较，如果直到null，每个元素都相等，则是回文链表。同时判断完之后需要将链表逆置回去。需要注意链表节点为单数与双数的处理。
法三代码：
/**
* [234. 回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/)
*
* @param head
* @return
*/
public boolean isPalindrome( ListNode head ) {
if ( head.next == null ) {
return true;
}
ListNode slow = head;
ListNode fast = head;
while ( fast.next != null && fast.next.next != null ) {
slow = slow.next;
fast = fast.next.next;
}
ListNode reverseStart = slow;
ListNode node = head;
// 如果是奇数个节点，此时fast在最后一个节点
// 可以用fast的下一个节点是否为空来判断整个链表节点个数是技术还是偶数
if ( fast.next == null ) {
// 需要将slow 指向下一个节点 再进行翻转
slow = slow.next;
ListNode temp = reverseList( slow);
while ( temp!=null ){
if(temp.val!=node.val){
// System.out.println(temp.val +"-"+ node.val);
return false;
}
temp=temp.next;
node=node.next;
}
reverseStart.next = reverseList( slow );
} else {
// 若节点个数为偶数，则slow 在上中点
// 需要返回以下中点为首的 翻转后的链表
//返回 slow.next后半部分链表
ListNode temp = reverseList( slow.next );
while ( temp!=null ){
if(temp.val!=node.val){
return false;
}
temp=temp.next;
node=node.next;
}
reverseStart.next = reverseList( slow );
}
return true;
}
public ListNode reverseList( ListNode head ) {
if ( head == null ) {
return head;
}
ListNode pre = null;
ListNode cur = head;
while ( cur != null ) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
代码更少的解法：
/**
* 优秀的解法
* https://labuladong.gitee.io/algo/2/17/19/
* @param head
* @return
*/
boolean isPalindromeByLa(ListNode head) {
ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null)
slow = slow.next;
ListNode left = head;
ListNode right = reverseList(slow);
while (right != null) {
if (left.val != right.val)
return false;
left = left.next;
right = right.next;
}
return true;
}
参考
如何判断回文链表
142.环形链表II
环形链表的快慢指针相遇的数学证明
环形链表问题（详细证明过程）
有环链表问题及其证明
链表是否有环 快指针走三步