《链表篇》---环形链表II(返回节点)

题目传送门

方法一：哈希表（与环形链表类似）

很容易就可以找到链表的相交位置。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }

        Set<ListNode> visited = new HashSet<>();
        while(head != null){
            visited.add(head);
            head = head.next;
            if(visited.contains(head)){
                return head;
            }            
        }
        return 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){
            if(fast.next != null){
                fast = fast.next.next;
            }else{
                return null;
            }
            slow = slow.next;

//当快指针和慢指针相遇的时候。
//我们新建一个指针指向头结点。此时我们让头指针和慢指针同时往后走。
//那么他们一定会相遇。此时我们再返回头结点。
            if(fast == slow){
                ListNode ptr = head;
                while(ptr != slow){
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;

    }
}