[数据结构与算法]链表环相关问题

1. 判断链表是否有环

• 环形链表

解法一 哈希表

• 将遍历过的节点存入哈希表，利用哈希表数据唯一性

 /**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        Set<ListNode> s = new HashSet<>();
        while(head != null){
            if(!s.add(head)) return true;
            head = head.next;
        }
        return false;
    }
}

解法二(最优解) 快慢指针

• 此解法空间复杂度O(1)， 时间复杂度O(n)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        ListNode slowPointer = head;
        ListNode fastPointer = head.next;
        while(slowPointer != fastPointer){
            if(fastPointer == null || fastPointer.next == null) //这里只需判断fastPointer
                return false;
            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next.next;
        }
        return true;
    }
}

2. 获取环的入口节点

• 剑指 Offer II 022. 链表中环的入口节点

题解参考

• 题解

Java实现

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow) {//判断出链表有环，快指针放到链表开始，然后快慢指针同速度前进
                fast = head;
                while(slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }
        return null;
    }
}

3. 计算环的长度

• 在解决前两个问题的基础上，此问题变得很简单了
• 参考文章

为什么快慢指针一定会相遇？

• 快慢指针慢指针和快指针一定会相遇