O(n) time O(1) space. A different approach to finding the start of cycle.


  • 1
    P

    The solution begins by first finding out if there is a cyle or not. If no cycle then return null. To find out the cycle use the slow, fast pointer technique. Once it has been established that cycle exists, find out the distance of the intersect node from the head of the list. Also find out the size of the loop.
    Now the question reduces to finding the common element in two linked lists. One list starts at head, and the other one starts at intersect node. To do this align the nodes such that they are both the same distance away from the end(intersect). Once this is done, you just have to increment and check if the nodes are equal or not.

    public class Solution {
        public ListNode detectCycle(ListNode head) {
            if (head == null) return head;
            //first check whether cycle exists or not
            ListNode first, second;
            first = second = head;
            while(true){
                first = first.next;
                if (second.next != null) second = second.next;
                else return null;
                if (second.next != null) second = second.next;
                else return null;
                if (first == second) break;//list contains a cycle break
            }
            
            //cycle exists store the intersect node
            ListNode intersect = first;
            first = head;
            int k = 1;//the distance of the intersect node from head
            while(true){
                if (first == intersect) break;
                first = first.next;
                k++;
            }
            //the intersection is at distance k away from the head;
            //now get the size of the loop
            int s = 0;first = intersect;
            while(true){
                first = first.next;
                s++;
                if (first == intersect) break;
            }
            //s is the size of the loop now
        
            //now the question reduces to find the first intersecting element
            //of two linked lists, list1 starts at head, list2 starts at intersect now
            
            //the first step is to align the nodes so they are at the same distance from the end(intersect node)
            first = head;second = intersect;
            if (s > k){
                for(int i = s; i < k;i++)
                    second = second.next;
            }else{
                for(int j = k; j < s; j++)
                    first = first.next;
            }
            while(true){
                if (first == second) return first;
                first = first.next;
                second = second.next;
            }
        }
    }

  • 0
    W

    Glad to share the same methods. Well, I think my code maybe more concise? Welcome to come to my share and make some comments.:)
    https://oj.leetcode.com/discuss/18393/share-my-o-n-complexity-and-constant-space-code-any-comments


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.