Concise JAVA solution, O(1) memory O(n) time


  • 140
    Z

    1, Get the length of the two lists.

    2, Align them to the same start point.

    3, Move them together until finding the intersection point, or the end null

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = length(headA), lenB = length(headB);
        // move headA and headB to the same start point
        while (lenA > lenB) {
            headA = headA.next;
            lenA--;
        }
        while (lenA < lenB) {
            headB = headB.next;
            lenB--;
        }
        // find the intersection until end
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }
    
    private int length(ListNode node) {
        int length = 0;
        while (node != null) {
            node = node.next;
            length++;
        }
        return length;
    }

  • 1
    J

    it`s a good answer~~but the running time is O(n+m+max[n.m]), right? I tried this in python, somehow it got better running time than two pointer solution


  • 0
    A

    Thats a perfect solution,thanks :)


  • 0
    C

    what is the two pointer solution?


  • 0
    B

    We have the same ideas! Even how we use two while loops to align the lists! I think this solution is great.


  • 1
    A

    Possible null pointer exception if two linked list do not have intersection.


  • 0
    T
    This post is deleted!

  • 0
    V

    @tethys it will return 4. in the code line
    "while (headA != headB) { "

    the two nodes will be equal when they have the same address (not the same stored value)


  • 0
    R

    Hi @jimmydada, what is the two pointer solution?


  • 0
    R

    so this solution make mistakes?


  • 0
    Z

    no, it's correct. You can have a try using the OJ. The example discussed above is a wrong example. if two links are 1-2-3-4 and 2-5-4, return 2 is correct.


  • 0
    E

    what if the two lists have more than one intersections? Shouldn't we find out all of them?


  • 1
    J

    You have a misunderstanding about the O(n) time. If a program runs in O(n) time, it does not mean it's running time equals to n. It means the running time equals to (an+b), where a and b can be any real numbers.
    Hope this helps you.
    If I make any mistakes, welcome to point out.


  • -1
    H

    if the two linked list is:
    1,2,3,4,5 and
    3,7,5
    it's will not work!


  • 0
    F

    the definition of the intersection is a bit confusing ...


  • 2
    S

    what if 1 2 3 4 and 2 3 4 5, we should return 2, but this will not


  • -1
    W

    while (headA != headB) is ok.
    But why
    while (headA.val != headB.val)
    can not work?


  • 0

    Very concise and intuitive! Better than tricky approach!


  • 0
    X

    @wangweichen you may add headA.next !=headB.next if you use while(headA.val!=headB.val).


  • 0
    K

    @hgfdodo This test case is incorrect. A list node has only one next pointer. So it can point to only one next node. Your test case is like

    0_1482919659710_IMG_20161228_050631.jpg

    which is incorrect because node with data 3 points to 2 nodes.(with data 4 and 7).
    From the common node onwards, both the lists become the same list.(like the example given in the question)


Log in to reply
 

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