Leetcode-142-Linked List Cycle II

Posted 2022-07-15

6~8 min read

Linked List Cycle II

leetcode: https://leetcode.com/problems/linked-list-cycle-ii/

Description:

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Idea:

**solution **

Step1: create slow and fast pointers, make fast pointer move two elements each time, and slow pointer move one element each time

Step2: use loop until the fast pointer point to null, but if there is a cycle, the fast pointer never point to null. At the same time, the slow index and fast index will meet in the cycle.

Step3: when ensure there is a cycle, set two new index, one pointer start from the list, the other one start from the node they meet. when they meet again, the node is the entrance of cycle.

Code:

/**
 * 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) {
        //set two pointer and make them start from the head
        ListNode fast = head;
        ListNode slow = head;
        //use fast index to traverse until it points to null
        while(fast != null && fast. next != null){
            //fast move two elements firstly, then slow index move one element each time
            fast = fast.next.next;
            slow = slow.next;
            //if they exists cycle, they will meet in the cycle
            if(fast == slow){
                //find the entrance node of the cycle.
                //set two pointer,, one form the meet node, the other one from the start
                ListNode index1 = slow;
                ListNode index2 = head;
                //when they meet, that's the entrance
                while(index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

Leetcode

Leetcode Linked List