参考链接：https://blog.csdn.net/Bruce_0712/article/details/107598682
https://leetcode-cn.com/problems/linked-list-cycle
链表定义
class ListNode{
int val;
ListNode next;
ListNode(int x){
this.val=x;
next=null;
}
}
循环链表将链表节点（注意是节点，不是节点里的值）存入到hashset中，如果元素添加不进去则证明有环
public static boolean hasCycle1(ListNode head){
//存入的是ListNode类型而不是值
HashSet<ListNode> hashSet = new HashSet<>();
while (head!=null){
if (!hashSet.add(head)){
return true;
}
head=head.next;
}
return false;
}
复杂度分析：
题目要求要使用空间复杂度O(1)的方法，可以使用快慢指针解决该问题。
解决思路：定义两个指针，一个指针每次移动一个位置为慢指针，一个指针每次移动两个位置为快指针。当两个指针相遇时就证明有环，如果快指针或者慢指针下一个节点为null，则证明无环。
为什么两个指针一定会相遇呢？
两个指针一旦进入环，遍历的时候相当于无限循环因为出不出来环啊。想象一下时钟，时针分针秒针在不同速度遍历时是不是会相遇呢？
public static boolean hasCycle2(ListNode head){
if (head==null || head.next==null){
return false;
}
//定义两个指针,快指针比慢指针多一步
ListNode slow = head;
ListNode fast = head.next;
while (slow!=fast){
if (fast==null||fast.next==null){
return false;
}
//快指针比慢指针多一步
slow=slow.next;
fast=fast.next.next;
}
return true;
}
复杂度分析
更有难度的一道题，检测环中判断入环点是哪个节点：https://leetcode-cn.com/problems/linked-list-cycle-lcci/
给定链表的头结点，然后反转链表，如下
输入：1→2→3→4→5→null
输出：null←1←2←3←4←5
链表结构
class LikendNode{
int val;
LikendNode next;
public LikendNode(int val){
this.val=val;
this.next=null;
}
}
直接反转，这种解法需要知道节点的前一个位置，然后将next指向前一个位置即可。
//null←1←2←3 4->5
//1.断开34的连接；2.将4的next指向前一个节点
public static LikendNode reverseLikenList(LikendNode head){
//由于单向链表需要存储前一个节点值
LikendNode prev = null;
LikendNode curr = head;
while (curr!=null){
//将节点4的next值保存下来
LikendNode next = curr.next;
//将节点3的引用赋值给节点4的next属性
curr.next=prev;
//将节点4的引用复制prev,供节点5反转
prev=curr;
//当前节点前进一位
curr=next;
}
//返回头节点值
return prev;
}
时间复杂度O(N)，空间复杂度O(1)
使用递归的方式，递归到尾结点，然后将引用(指针反转即可)。如1→2→3→4→5→null，递归到节点5，然后反转4←5，依次出栈就可以。如下动画
//1→2→3→4→5→null
public static LikendNode reverseLikendList1(LikendNode head){
if (head==null || head.next==null){
return head;
}
//递归,当递归到节点5时,因为head.next==null开始返回节点5
//出栈节点4
// 1→2→3→4←5
LikendNode newHead = reverseLikendList1(head.next);
//将5.next=4,即4←5
head.next.next=head;
//然后将4->5的引用断开
head.next=null;
return newHead;
}
注意newHead的值，只返回节点5，因为是从return head得到的，之后的出栈没有修改newHead值。如果不太明白的话，用IDEA的DEBUG模式看入栈出栈过程就明白了。
复杂度分析
相对比迭代法需要额外的空间复杂度。
这个是我当时的面试题，
给定左右两个节点的位置（注意不是值，否则还要考虑值重复问题），反转区间的链表
输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]
输入：head = [5], left = 1, right = 1 输出：[5]
public ListNode reverseBetween(ListNode head, int left, int right) {
//定义一个虚拟头结点
ListNode dummyNode = new ListNode(0);
dummyNode.next=head;
//1.定义两个指针,守卫节点(grade)和指针节点(point)
//守卫节点控制边界头插法,指针节点删除移动节点
ListNode g = dummyNode;
ListNode p = dummyNode.next;
//2.移动两个节点到指定位置。
//将g移动到第一个要反转的节点的前面,将p移动到第一个要反转的节点位置上
for (int step=0;step<left-1;step++){
g=g.next;p=p.next;
}
//3.头插法插入节点
//将p后面的元素删除,添加到g的后面,就是头插法
for (int i = 0;i<right-left;i++){
//删除p后面的元素
ListNode removed = p.next;
p.next = p.next.next;
//将p后面的元素添加到g后面
removed.next=g.next;
g.next=removed;
}
return dummyNode.next;
}