Share my simple java solution O(n) time, O(1) space


  • 65
    A
    1. Scan both lists
    2. For each list once it reaches the end, continue scanning the other list
    3. Once the two runner equal to each other, return the position

    Time O(n+m), space O(1)

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    		if( null==headA || null==headB )
    			return null;
    		
    		ListNode curA = headA, curB = headB;
    		while( curA!=curB){
    			curA = curA==null?headB:curA.next;
    			curB = curB==null?headA:curB.next;
    		}
    		return curA;
        }

  • 0
    N

    great! transform of determining a circle list .


  • 0
    X

    What if both lists are not null but still no matches exist?


  • 2
    L

    This algorithm is sooooo perfect!

    I was wonder if the running time is O(n+m), but later I figured out that the actually running time is just:

    1. m+n for non-intersection case

    2. With intersection:

      Suppose for LL-A, it's a+b=n, a is the # of nodes before intersection

      Suppose for LL-B, it's c+b=m, c is the # of nodes before intersection

    Thus the actual running time is a+b+c = n+c = m+a.

    Actually, when b=0, this just stands for the case with no intersection with a+b+c=n+m


  • 0
    This post is deleted!

  • 0
    R

    What if there is no intersection between the two lists? (the lists are not null)
    How does the code exit the while loop, since the condition being testes is that an intersection be found?


  • 0

    This algorithm is really very perfect! As a supplement, I think the following approach is an idea to solve the problem if there is no intersection between the two lists.

    We assume that the length of headA is 'm' and the length of headB is 'n', follow the above ideas, we will find the node at which the intersection of two singly linked lists begins within 'm + n - 1' steps. So the corresponding C++ code is:

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL)
            return NULL;
        if (headA == headB)
            return headA;
    	ListNode *curA = headA;
    	ListNode *curB = headB;
    	int lenA = 0, lenB = 0;
    	while (curA != NULL) {
    		++lenA;
    		curA = curA->next;
    	}
    	while (curB != NULL) {
    		++lenB;
    		curB = curB->next;
    	}
    	curA = headA;
    	curB = headB;
    	for (int step = 0; step != lenA + lenB; ++step) {
    		curA = curA ? curA->next : headB;
    		curB = curB ? curB->next : headA;
    		if (curA == curB)
    			return curA;
    	}
    	return NULL;
    }
    

  • 5

    In the while loop, just by adding a simple test, the loop could stop if there's no intersection.

    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            ListNode* a = headA;
            ListNode* b = headB;
            
            if (a == NULL || b == NULL){
                return NULL;
            }
            
            while (a != b){
                a = (a == NULL ? headB : a->next);
                b = (b == NULL ? headA : b->next);
                
                if (a == headA && b == headB){
                    return NULL;
                }
            }
            
            return a;
        }
    };

  • 1
    J

    The code will exit the while loop when curA and curB are both null.


  • 0
    S

    Why down votes? This actually works well.


  • 0
    S

    I am a little confuse about the stop condition. In the while, it seems that a never assigned to headA and b never assigned to headB, why it will return null when there is no intersection?


  • 0
    C

    it seems that without that stop condition, the code will still be accepted.
    but i think add a variable like "count" to count the time a==headB && b=headA is ok to detect non-intersection


  • 1
    Z

    i think the stop condition should be
    a == null && b == null than return null
    means two pointers have finished scan list A and B


  • 0
    J

    This is a wonderful, much cleaner piece of code


  • 0
    H

    great solution, however seems to use up more time though. not sure why


  • 0
    I

    What if there is no intersection?
    Even if you add a test like this to stop the loop, it would at worst take lengthA * lengthB steps if A is one node longer or shorter than B

    while (a != b){
                a = (a == NULL ? headB : a->next);
                b = (b == NULL ? headA : b->next);
    
                if (a == headA && b == headB){
                    return NULL;
                }
            }
    

  • 0
    S

    I didn't understand why we cannot use headA and headB directly. I tried to delete curA and curB, and it returns the wrong answer:

    Input:
    No intersection: [1,3,5,7,9,11,13,15,17,19,21] [2]
    Output:
    Intersected at '5'
    Expected:
    No intersection


  • 0
    A

    @iamty Because if there is no intersection, a and b will both run (m+n) and then both of their .next node equal NULL, then will quit this loop and return NULL to function.


Log in to reply
 

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