• 30.2%

Write a program to find the node at which the intersection of two singly linked lists begins.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Simple C++ solution (5 lines)

Move cur1 (cur2) forward from headA (headB) and loop back to headB (headA), eventually cur1 and cur2 will meet at the intersection point or nullptr.

My accepted simple and shortest C++ code with comments explaining the algorithm. Any comments or improvements?

#### cpp

46ms, 46.30%, October 15, 2016

My accepted simple and shortest C++ code with comments explaining the algorithm. Any comments or improvements?

https://discuss.leetcode.com/topic/38444/simple-c-solution-5-lines

Simple C++ solution (5 lines)

Move cur1 (cur2) forward from headA (headB) and loop back to headB (headA), eventually cur1 and cur2 will meet at the intersection point or nullptr.

#### python

the idea is if you switch head, the possible difference between length would be countered.

On the second traversal, they either hit or miss.

if they meet, pa or pb would be the node we are looking for,

if they didn’t meet, they will hit the end at the same iteration, pa == pb == None, return either one of them is the same,None

my code:

#### java

https://discuss.leetcode.com/topic/28067/java-solution-without-knowing-the-difference-in-len

Java solution without knowing the difference in len!

I found most solutions here preprocess linkedlists to get the difference in len.
Actually we don’t care about the “value” of difference, we just want to make sure two pointers reach the intersection node at the same time.

We can use two iterations to do that. In the first iteration, we will reset the pointer of one linkedlist to the head of another linkedlist after it reaches the tail node. In the second iteration, we will move two pointers until they points to the same node. Our operations in first iteration will help us counteract the difference. So if two linkedlist intersects, the meeting point in second iteration must be the intersection point. If the two linked lists have no intersection at all, then the meeting pointer in second iteration must be the tail node of both lists, which is null

Below is my commented Java code:

https://discuss.leetcode.com/topic/5492/concise-java-solution-o-1-memory-o-n-time

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

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

https://discuss.leetcode.com/topic/11626/share-my-simple-java-solution-o-n-time-o-1-space

Share my simple java solution O(n) time, O(1) space

1. Scan both lists
2. For each list once it reaches the end, continue scanning the other list
3. Once the two runner equal to each other, return the position

Time O(n+m), space O(1)