- 30.2%

https://leetcode.com/problems/intersection-of-two-linked-lists/description/

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

1 | For example, the following two linked lists: |

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.

方法一：

剑指offer 37

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.

此代码的巧妙之处在于，1，头尾相接，2，判断条件是cur1!=cur2

1 | ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { |

我的代码实现：

1 | class Solution { |

另一种实现方法

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

1 | ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) |

#### cpp

46ms, 46.30%, October 15, 2016

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

1 | ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) |

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.

1 | ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { |

#### python

https://discuss.leetcode.com/topic/13419/concise-python-code-with-comments

Concise python code with comments

1 | class Solution: |

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:

1 | # Definition for singly-linked list. |

#### 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:

1 | public ListNode getIntersectionNode(ListNode headA, ListNode headB) { |

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

1 | public ListNode getIntersectionNode(ListNode headA, ListNode headB) { |

1 | /** |

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

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

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

1 | public ListNode getIntersectionNode(ListNode headA, ListNode headB) { |