环形链表专题

一、问题1

给定一个链表，判断一个链表中是否有环

1.算法思路

（1）判断是否存在重复节点

通过检查一个节点此前是否被访问来判断是否为环形链表，可以使用哈希表来存储访问过的节点

（2）快慢指针

通过快慢指针遍历链表，慢指针每次移动一步，而快指针每次移动两步；如果链表中不存在环，最终快

指针将会最先达到尾部，此时返回Fasle即可；如果链表中存在环，最终快慢指针一定会相遇

2.代码实现

//元素判重法
public boolean hasCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<ListNode>();
    while (head != null) {
        if (visited.contains(head)) {
            return true;
        } else {
            visited.add(head);
        }
        head = head.next;
    }
    return false;
}
//分析，时间复杂度是O（n），对链表中的每个元素最多访问一次，向哈希表中添加一个元素为O(1)
//空间复杂度为O（n）,最多将链表中的所有元素均添加到哈希表中

//快慢指针法
public boolean hasCycle(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;
}

//分析：空间复杂度是O（1）,只使用了快慢指针两个节点
//时间复杂度O（n）,实际上快慢指针算法的时间复杂度要大于等于判重算法

二、问题2

给定一个链表，返回链表开始入环的第一个节点，如果链表无环，则返回null

1.算法思路

（1）判重法找出入口节点

通过检查一个节点此前是否被访问来判断该点是否为环的入口点，可以使用哈希表来存储访问过的节点

（2）快慢指针

第一步时通过快慢指针遍历链表，慢指针每次移动一步，而快指针每次移动两步,先判断此单链表中是

否有环，无环则直接返回空值，有环就返回环的入口节点；

第二步是让快指针重新从头结点出发，和慢指针（此时指向相遇节点）同时走，每次走一步，当再相遇

时的节点就是环的入口节点，具体原理如下图

(3)引用计数解法

链表中环的入口节点在程序中恰好被引用5次

2.代码实现

#快慢指针解题
def detectCycle(self, head):
   fast, slow = head, head  #快慢节点进行初始化为头结点
   while True:
      if not (fast and fast.next): 
        return None   #链表中是没有环的
      fast, slow = fast.next.next, slow.next
      if fast == slow: #第一个相遇节点
        break
      fast = head      #将快指针初始化初始节点
   while fast != slow:
        fast, slow = fast.next, slow.next   #快慢指针再次相遇的节点就是环的入口节点
   return fast
#时间复杂度O（n）、空间复杂度O（1）
    
#引用计数解题
def detectCycle(self, head: ListNode) -> ListNode:
   if not head:
      return None
   while head.next:
   	  if sys.getrefcount(head) >= 5:
        return head
      head = head.next
   return None
#分析：在遍历链表的过程中目标节点（环的入口节点）被其两个前驱节点（head.next）分别引用一次
#被当前节点引用一次（head）
#在当做参数传入函数时被引用一次，在函数内部又被引用一次，总共5次
#算法的时间复杂度O(n)、空间复杂度O（1）

三、双指针的其他常见问题

输入一个链表，输出该链表中倒数第K个节点

public ListNode getKthFromEnd(ListNode head, int k) {
   if(head == null || k == 0){
       return null;
     }
   ListNode slow = head,fast = head;
   for(int i = 1;i<k;i++){
       fast = fast.next;
     }
   while(fast.next != null){
       fast = fast.next;
       slow = slow.next;
     }
   return slow;
}
//分析：快、慢两个指针，快指针先走k-1步，然后快慢指针同时走；当快指针走到结尾时
//此时慢指针指向的节点就是倒数第K个节点
//时间复杂度O（n）、空间复杂度O（1）