LeetCode 142. Linked List Cycle II (javascript solution)

Description:

Given 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 po…


This content originally appeared on DEV Community and was authored by codingpineapple

Description:

Given 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. Note that pos is not passed as a parameter.

Notice that you should not modify the linked list.

Solution:

Time Complexity : O(n)
Space Complexity: O(1)

var detectCycle = function(head) {
    let slow = head;
    let fast = head;
    while(fast && fast.next && fast.next.next){
        slow = slow.next;
        // Move fast pointer twice as fast as slow pointer and if there is a cycle, the fast will eventually meet slow at a node in the cycle but not necessarily the node that starts the cycle
        fast = fast.next.next;
        // Once we determine there is a cycle we must find where the cycle starts
        if(slow === fast){
            // Move slow pointer to the head
            slow = head;
            // Move both fast and slow pointer one node at a time and they will meet at the node where the cycle starts
            while(slow !== fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
};


This content originally appeared on DEV Community and was authored by codingpineapple


Print Share Comment Cite Upload Translate Updates
APA

codingpineapple | Sciencx (2021-04-10T05:18:20+00:00) LeetCode 142. Linked List Cycle II (javascript solution). Retrieved from https://www.scien.cx/2021/04/10/leetcode-142-linked-list-cycle-iijavascript-solution/

MLA
" » LeetCode 142. Linked List Cycle II (javascript solution)." codingpineapple | Sciencx - Saturday April 10, 2021, https://www.scien.cx/2021/04/10/leetcode-142-linked-list-cycle-iijavascript-solution/
HARVARD
codingpineapple | Sciencx Saturday April 10, 2021 » LeetCode 142. Linked List Cycle II (javascript solution)., viewed ,<https://www.scien.cx/2021/04/10/leetcode-142-linked-list-cycle-iijavascript-solution/>
VANCOUVER
codingpineapple | Sciencx - » LeetCode 142. Linked List Cycle II (javascript solution). [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/04/10/leetcode-142-linked-list-cycle-iijavascript-solution/
CHICAGO
" » LeetCode 142. Linked List Cycle II (javascript solution)." codingpineapple | Sciencx - Accessed . https://www.scien.cx/2021/04/10/leetcode-142-linked-list-cycle-iijavascript-solution/
IEEE
" » LeetCode 142. Linked List Cycle II (javascript solution)." codingpineapple | Sciencx [Online]. Available: https://www.scien.cx/2021/04/10/leetcode-142-linked-list-cycle-iijavascript-solution/. [Accessed: ]
rf:citation
» LeetCode 142. Linked List Cycle II (javascript solution) | codingpineapple | Sciencx | https://www.scien.cx/2021/04/10/leetcode-142-linked-list-cycle-iijavascript-solution/ |

Please log in to upload a file.




There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.