Java O(n) time solution and O(1) space using idea in "Linked Cycle List II"


  • 1
    B

    The idea came from this problem: https://oj.leetcode.com/problems/linked-list-cycle-ii/

    The current problem can be formalized to match that problem: just connect the tail of list A to the head of B. Then find the starting point of the cycle which will be the same as the intersection of the original lists. Of course at the and you must restore the original lists, removing the cycle.


  • 0
    H
    public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        int times = 0;
        while(times<=1){
            if(A==B)
              return A;
            if(A==null){
                A=headB;
                times++;
            }
            else
              A=A.next;
            if(B==null)
              B=headA;
            else
              B=B.next;              
    
    
        }
        return null;
    }
    

    }


Log in to reply
 

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