Intersection of Two Linked Lists


  • 0

    Click here to see the full article post


  • 0
    L

    wow, I like the third solution so much.


  • 1
    F

    Another solution is this: first find the lengths of the two lists and calculate the difference. Then make the delta as the starting point in the longer list, then move in parallel in both lists until links to next node match. Once you find a match, that's the location where the intersection happens. This will give a time complexity of O(max(m,n)) while still keeping the space complexity at O(1).


  • 0
    R

    There is also a solution to reverse the list, search for the overlap and reverse them again before returning the results


  • 0
    I

    @filizk Yeah, I have the same solution. I like this question, it has so much different ways to solve it!


  • 0
    A

    @RADUIONESCU I like your idea of reversing the list and look for the last element after which the values differ in these lists. The running time will be O(M+N) with space O(1). I think this idea should be listed as the 4th solution here.


  • 0
    T

    @RaduIonescu, @acheiver you can't reverse it by O(1) space,


  • 0
    Z

    Does anyone receive the "Memory exceeds limit" error?


  • 0
    M

    class Solution(object):
    def getIntersectionNode(self, headA, headB):
    """
    :type head1, head1: ListNode
    :rtype: ListNode
    """
    A=headA
    B=headB
    a=1
    b=1
    if A==None or B==None:
    return None
    while A.next!=None:
    A=A.next
    a+=1
    while B.next!=None:
    B=B.next
    b+=1
    if A!=B:
    return None

        A=headA
        B=headB
        if a>b:
            for i in range(a-b):
                A=A.next
        else:
            for i in range(b-a):
                B=B.next
        while (A!=B):
            A=A.next
            B=B.next
        return A
    

    Why do I get ''Memory Limit Exceeded''?


  • 0
    M

    class Solution(object):
    def getIntersectionNode(self, headA, headB):
    """
    :type head1, head1: ListNode
    :rtype: ListNode
    """
    A=headA
    B=headB
    a=1
    b=1
    if A==None or B==None:
    return None
    while A.next!=None:
    A=A.next
    a+=1
    while B.next!=None:
    B=B.next
    b+=1
    if A!=B:
    return None
    A=headA
    B=headB
    if a>b:
    for i in range(a-b):
    A=A.next
    else:
    for i in range(b-a):
    B=B.next
    while (A!=B):
    A=A.next
    B=B.next
    return A
    Why do I get ''Memory Limit Exceeded''?


  • 0
    M

    A=headA
    B=headB
    a=1
    b=1
    if A==None or B==None:
    return None
    while A.next!=None:
    A=A.next
    a+=1
    while B.next!=None:
    B=B.next
    b+=1
    if A!=B:
    return None
    A=headA
    B=headB
    if a>b:
    for i in range(a-b):
    A=A.next
    else:
    for i in range(b-a):
    B=B.next
    while (A!=B):
    A=A.next
    B=B.next
    return A
    Why do I get ''Memory Limit Exceeded''?


  • 0
    E

    As a first step; I traverse both linked lists and find their end node. My code returns None if the end nodes are not equal. The 43rd test has two very long separate linked lists; my code fails at the first step due to 'Memory Limit Exceeded'. So, I believe the memory limitat was set wrong for this question; I tried every possible solution with python; they all failed due to the memory limit.


  • 0
    K

    @filizk Calculating the lengths of the lists takes O(m + n) time, so that approach is no better.


  • 0
    R

    Here is my solution with time complexity O(m + n) and space O(1):

    1. Traverse list A to find the tail of A (tailA), set tailA's next to headA, i.e. convert list A to a cycle.
    2. Use the same solution to problem 142. Linked List Cycle II: traverse from headB to find out whether list B contains the cycle or not. If not, there is no intersection between A and B, return null; otherwise, return the node where the cycle begins. In either case, set tailA's next back to null before return.

  • 0

    @toynlou7
    "@RaduIonescu, @acheiver you can't reverse it by O(1) space,"
    A linked list can't be reversed with O(1) space?
    Please provide proof.


  • 0
    F

    Another solution: traverse each list to get their length.
    Then move the head of the longer one so that they have the same length.
    Then move by one item on each list until their end, and return as soon as a node is the same on both lists.


  • 0
    D

    My solution:
    class Solution {
    public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode * a = headA;
    ListNode * b = headB;
    int count = 0;

        if(a == NULL || b == NULL)
            return NULL;
        
        while (a != b)
        {
            a = a->next;
            b = b->next;
            if (a == NULL)
            {
                a = headB;
                count ++;
            }
            if (b == NULL)
                b = headA;
            if (count == 2)
                return NULL;
        }
        return a;
    }
    

    };


  • 0
    Z

    Actually, i found this problem simple becuase it assums that all intersaction at the end of the list.So,we can just use 2 reverse process to scan 2 list from beginning one by one.Then,reverse the (may be truncated) list to get answer;My code is a little lengthy,but pricipal may be clear

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA==null||headB==null) return null;
    ListNode la=reverseNode(headA);
    showList("la",la);
    ListNode save=la;
    ListNode lb=reverseNode(headB);
    showList("lb",lb);
    if(la.val!=lb.val) return null;
    while (la.next!=null&&lb.next!=null){
    if(la.next.val==lb.next.val){
    la=la.next;
    lb=lb.next;
    }else {
    System.out.println("we quest "+la.val);

                break;
            }
        }la.next=null;
        return reverseNode(save);
    }
    public ListNode reverseNode(ListNode head) {
        if(head==null) return null;
        ListNode node = new ListNode(head.val);
        ListNode a = null;
        while (head.next!= null) {
            ListNode back = node;
            head = head.next;
            node = new ListNode(head.val);
            node.next = back;
        }
        return node;
    }

  • 0
    V

    Python Solution:
    How about this one ?

    class Solution(object):
    def getIntersectionNode(self, headA, headB):
    dict = {}
    while headA is not None:
    dict[headA] = 1
    headA = headA.next

        while headB is not None:
            if headB in dict:
                return headB
            else:
                headB = headB.next

  • 0
    Y

    The third approach assumes the intersection appears at the end of lists, but the description of this problem don't give this assume.


Log in to reply
 

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