单链表的环是否存在以及找出环的交点

发表于 | 阅读次数 | 阅读数

判断一个链表是否存在环

/**
 * Created by hzdmm on 2017/9/29.
 * Given a linked list, determine if it has a cycle in it.
 * <p>
 * Follow up:
 * Can you solve it without using extra space?
 * 判断一个链表里面是否有环
 */
public class LinkedListCycle_141 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public boolean hasCycle(ListNode head) {
        if (head==null){
            return false;
        }
        ListNode fast = head;
        ListNode slow =head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if (fast==slow){
                return true;//如果存在环,两个指针一快一慢肯定会相交
            }
        }
        return false;
    }
}

找到链表的环的交点

public ListNode detectCycle(ListNode head) {
    if (head==null) return null;
    ListNode fast = head;
    ListNode slow = head;
    while (fast!=null&&fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;
        if (fast==slow){//先找到相交
            fast = head;//fast重置回起点
            while (fast!=slow){//slow离相交点X 起点离交点为a
                //slow=s 和 fast=ns a+x=s   2s=s+nr
                fast=fast.next;
                slow=slow.next;
            }
            return fast;
        }
    }
    return null;
}
0%