如何判断链表有坏换

一、直接遍历

从头遍历，没当遍历到新的节点时，从头遍历，查看是否有重复的节点，如果有，就说明有环

时间复杂度：O(n2)

空间复杂度 O(1)

二、创建Hashset集合

遍历链表，把新的节点放在Hashset中，如果Hashset中存在，这说明有环

时间复杂度：O(n)

空间复杂度 O(n)

三、追击问题

创建两个指针，p1和p2，同时只想头节点，然后开始循环，p1每次向前移动一个元素，p2每次向前移动两个元素，然后比较两个指针指向的元素是否相同，如果相同则说明有环。

原因：追击问题，快的指针一定会追上慢的指针。

时间复杂度：O(n)

空间复杂度：O(1)

/**
 * @author: daixyhymn
 * @description:
 * @date: 2020/11/6 15:14
 */
public class Cycle {
  public static boolean cicyle(Node head){
    Node p1 = head;
    Node p2 = head;
    while(p2 != null && p2.next != null){
      p1 = p1.next;
      p2 = p2.next.next;
      if(p1 == p2) return true;
    }
    return false;
  }

  /*
  节点
  */
  private static class Node{
    int data;
    Node next;
    Node(int data){
      this.data = data;
    }
  }
}

1、判断环的长度

从两个指针第一次相遇的地方开始，其中一个指针开始向前每次移动一个位置，并统计走的步数，当两个指针再次相遇时，统计出来的步数就是节点的长度。

2、如果链表有环，如何求出入环点？

D:头节点到入环的距离

S1:入环点到首次相遇的距离

S2：首次相遇到入环点的距离

那么：

当两个指针首次相遇时，各自所走的距离时多少呢？

所以：

当两个指针首次相遇时，让其中一个指针回到头节点，然后两个指针每次只移动一步，比较他们所知的节点，如果两个指针指向的时同一个节点，这个节点就是入环点