# Python solution for intersection of two singly linked lists

• ``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @param two ListNodes
# @return the intersected ListNode
lenA,lenB = 0,0
while curA is not None:
lenA += 1
curA = curA.next
while curB is not None:
lenB += 1
curB = curB.next
if lenA > lenB:
for i in range(lenA-lenB):
curA = curA.next
elif lenB > lenA:
for i in range(lenB-lenA):
curB = curB.next
while curB != curA:
curB = curB.next
curA = curA.next
return curA
``````

The solution is straightforward: maintaining two pointers in the lists under the constraint that both lists have the same number of nodes starting from the pointers. We need to calculate the length of each list though. So O(N) for time and O(1) for space.

• Very clear code! I like it!

I used to code in Java, not very familiar with Python grammar but had the same algorithm as you did, thanks for implementing it out.

• Well Done! It seems that Python show a more succinct code than C++(I used to it). No pointer in Python makes it more happy.:-)

• good implement

• Good job! I could easily follow your thought! Thanks a lot!

• you are so smart.

• What if there is no intersection found? Shouldn't we compare the tails of the linkedlist and return False if tails are not the same?

• Now it got MLE.

• @jedihy that's right~

• Now it got MLE.

• @peaceful Your code cannot pass the test. My code is similar with yours, which cannot pass. Then I copied your code to run and it also cannot pass. It gives memory limit exceed error.

• Here is the implementation in C.

``````struct ListNode *getIntersectionNode(struct ListNode *headA,
{
int lenA = 0, lenB = 0;

/* Find the length of the lists */
while (node1 || node2){
if (node1) {
node1 = node1->next;
lenA++;
}
if (node2) {
node2 = node2->next;
lenB++;
}
}

/* Move the first or second list pointer based on the difference */
/* Scan forward to cover the difference in length */
while (lenA > lenB) {
node1 = node1->next;
--lenA;
}
while (lenB > lenA) {
node2 = node2->next;
--lenB;
}

/* Now scan both the lists together to find the intersection */
while (node1 != node2 && node1 && node2) {
node1 = node1->next;
node2 = node2->next;
}

/* Return the intersection */
return node1;
}
``````

• @songgaoxian Yeah, same question. This is a weird situation.

• @onerhao Yes, same problem, it should pass the test.

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