leetcode 142. 环形链表 2

哈哈，这题和环形链表1差不多 ，链表1详情参见  https://blog.****.net/a66666_/article/details/105211023

解法1. 快慢指针 （建议不要直接复制到leetcode，会报错，自己手打一遍）

时间复杂度O(N)  空间复杂度O(1)

 

public ListNode detectCycle(ListNode head) {

        ListNode walker = head;

        ListNode runner = head;

        while (runner != null && runner.next != null) {

            walker = walker.next;

            runner = runner.next.next;

            if (walker == runner) {

                ListNode walker2 = head;

                while (walker != walker2) {

                    walker = walker.next;

                    walker2 = walker2.next;

                }

                return walker;

            }

        }

        return null;

    }

相比 环形链表1的解法多了下方的代码

ListNode walker2 = head;

                while (walker != walker2) {

                    walker = walker.next;

                    walker2 = walker2.next;

                }

因为环形链表1快慢指针相遇的节点并不是连接的那个节点

如图所示，p为快慢指针相遇节点，q为连接节点，而连接节点由公式 a+2b+c == 2(a+b)可推出a == c

解法二：哈希表

时间复杂度O（N），空间复杂度O(N)

 

public ListNode detectCycle(ListNode head) {

        Set<ListNode> node = new HashSet<ListNode>();

        while (head != null) {

            if (node.contains(head)) {

                return head;

            }

            node.add(head);

            head = head.next;

        }

        return null;

    }