# Intersection of Two Linked Lists

• wow, I like the third solution so much.

• 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).

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

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

• @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.

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

• Does anyone receive the "Memory exceeds limit" error?

• class Solution(object):
"""
:rtype: ListNode
"""
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
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''?

• class Solution(object):
"""
:rtype: ListNode
"""
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
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''?

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
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''?

• 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.

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

• 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.

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

• 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.

• My solution:
class Solution {
public:
int count = 0;

``````    if(a == NULL || b == NULL)
return NULL;

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

};

• 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

showList("la",la);
ListNode save=la;
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);
}
ListNode a = null;
ListNode back = node;
node.next = back;
}
return node;
}``````

• Python Solution:

class Solution(object):
dict = {}
``````    while headB is not None: