Intersection of Two Linked Lists


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

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


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 NoneA=headA B=headB if a>b: for i in range(ab): A=A.next else: for i in range(ba): B=B.next while (A!=B): A=A.next B=B.next return A
Why do I get ''Memory Limit Exceeded''?

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(ab):
A=A.next
else:
for i in range(ba):
B=B.next
while (A!=B):
A=A.next
B=B.next
return A
Why do I get ''Memory Limit Exceeded''?

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(ab):
A=A.next
else:
for i in range(ba):
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):
 Traverse list A to find the tail of A (tailA), set tailA's next to headA, i.e. convert list A to a cycle.
 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.

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; }
};

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==nullheadB==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; }