链表算法相关

链表算法相关 反转链表

时间复杂度：O(n) ,其中 nn 是链表的长度。需要遍历链表一次。空间复杂度：O(1)

给定一个链表的头节点，反转链表后，最后返回新链表的头节点；

const reverseList = head =>{
  let prev =null;
  let curr =head;
  while(curr){
   const next = curr.next;
   prev=curr;
   curr=next;
}
  return prev;
}

判断链表是否有环

利用快慢指针，快指针每次循环进2 ，慢指针每次进1 ，

类似：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。

const hasCycle = head =>{
let fast=head;
let slow =fast;
while(fast!==null&&fast.next!==null){
  slow=slow.next;
  fast=fast.next.next;
  if(fast===slow){
   return true ;
   }
}
  return false;
}

一个有环链表，找出入环点

由上一个确认环的过程，存在快指针 A 每次走两个节点，慢指针每次走一个节点，假设在W点相遇，此时 快指针A 走的路程 x+y + n *(y+z) = 2 （x+y） , 也即 入环点 x=n(y+z) - y
假设 此时有一个点point 从环head 处 开始 向入环点移动，同时慢指针从W 点 也也同样的速度 移动。x = (n-1) * (y+z) + z ，很容易看出 慢指针在环内走了 n-1圈 并多走了z 距离 ，两者在入环点一定相遇 ，那么确定入环点需要两层循环即可

const detectCycle = (head) => {
  let fast = head;
  let slow = head;
  while (fast !== null && fast.next !== null) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast === slow) {
      let point = head;
      while (point !== slow) {
        point = point.next;
        slow = slow.next;
      }
      return point;
    }
  }
};