Java solution without knowing the difference in len!


  • 580
    H

    I found most solutions here preprocess linkedlists to get the difference in len.
    Actually we don't care about the "value" of difference, we just want to make sure two pointers reach the intersection node at the same time.

    We can use two iterations to do that. In the first iteration, we will reset the pointer of one linkedlist to the head of another linkedlist after it reaches the tail node. In the second iteration, we will move two pointers until they points to the same node. Our operations in first iteration will help us counteract the difference. So if two linkedlist intersects, the meeting point in second iteration must be the intersection point. If the two linked lists have no intersection at all, then the meeting pointer in second iteration must be the tail node of both lists, which is null

    Below is my commented Java code:

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //boundary check
        if(headA == null || headB == null) return null;
        
        ListNode a = headA;
        ListNode b = headB;
        
        //if a & b have different len, then we will stop the loop after second iteration
        while( a != b){
        	//for the end of first iteration, we just reset the pointer to the head of another linkedlist
            a = a == null? headB : a.next;
            b = b == null? headA : b.next;    
        }
        
        return a;
    }

  • 1
    J

    This is a very clever and easy to read solution. You da man!


  • 3
    Y

    what is the intuition behind this? do you have a mathematical proof?


  • 0
    G
    This post is deleted!

  • 0
    B
    This post is deleted!

  • 18
    P

    Clever, the two iterations will both run for listA.length + listB.length and will reach the intersection point at the same time after switching the pointer.


  • 0
    Y

    this runtime should be O(n^2) thought


  • 17
    5

    NO, it's O(m+n)


  • 6
    H

    I think they both run for listA.length + listB.length-commonlength(listA&listB).


  • 1
    C

    Hi man! Brilliant solution! You deserve all the credits!


  • 71
    Z

    You can prove that: say A length = a + c, B length = b + c, after switching pointer, pointer A will move another b + c steps, pointer B will move a + c more steps, since a + c + b + c = b + c + a + c, it does not matter what value c is. Pointer A and B must meet after a + c + b (b + c + a) steps. If c == 0, they meet at NULL.
    Thanks, hpplayer. This solution is very smart.


  • 0
    L

    so smart! like it


  • 0
    B
    This post is deleted!

  • 0
    H

    Both pointers will be null in this case


  • 0
    E

    really nice solution


  • 1
    M

    This really nice solution. Though it's a easy problem, such solution is hard to come up with.


  • 18
    S

    I have a problem.

    What if the two lists are [1,2],[3],then the two list will never meet. And the loop will never end.


  • 3
    M

    a will be null and b will be null too, which stops loop.


  • 0
    L

    No,just listA.length + listB.length.


  • 1
    D

    One of the best solution I found on the internet. That change to headA and headB is the trick here. +1 for the ingenuity.


Log in to reply
 

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