160. Intersection of Two Linked Lists

  • 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
2
3
4
5
6
7
8
For example, the following two linked lists:

A: a1 → a2

c1 → c2 → c3

B: b1 → b2 → b3
begin to intersect at node c1.

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
2
3
4
5
6
7
8
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *cur1 = headA, *cur2 = headB;
while(cur1 != cur2){
cur1 = cur1?cur1->next:headB;
cur2 = cur2?cur2->next:headA;
}
return cur1;
}

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==NULL || headB==NULL) return NULL;
ListNode* p1 = headA, *p2 = headB;
if(p1==p2) return p1;
while(p1 || p2){
if(p1)
p1 = p1->next;
else
p1 = headB;
if(p2)
p2 = p2->next;
else
p2 = headA;
if(p1==p2)
return p1;
}
}
};

另一种实现方法

https://discuss.leetcode.com/topic/5527/my-accepted-simple-and-shortest-c-code-with-comments-explaining-the-algorithm-any-comments-or-improvements

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
{
ListNode *p1 = headA;
ListNode *p2 = headB;

if (p1 == NULL || p2 == NULL) return NULL;

while (p1 != NULL && p2 != NULL && p1 != p2) {
p1 = p1->next;
p2 = p2->next;

//
// Any time they collide or reach end together without colliding
// then return any one of the pointers.
//
if (p1 == p2) return p1;

//
// If one of them reaches the end earlier then reuse it
// by moving it to the beginning of other list.
// Once both of them go through reassigning,
// they will be equidistant from the collision point.
//
if (p1 == NULL) p1 = headB;
if (p2 == NULL) p2 = headA;
}

return p1;
}

cpp


46ms, 46.30%, October 15, 2016

https://discuss.leetcode.com/topic/5527/my-accepted-simple-and-shortest-c-code-with-comments-explaining-the-algorithm-any-comments-or-improvements

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
{
ListNode *p1 = headA;
ListNode *p2 = headB;

if (p1 == NULL || p2 == NULL) return NULL;

while (p1 != NULL && p2 != NULL && p1 != p2) {
p1 = p1->next;
p2 = p2->next;

//
// Any time they collide or reach end together without colliding
// then return any one of the pointers.
//
if (p1 == p2) return p1;

//
// If one of them reaches the end earlier then reuse it
// by moving it to the beginning of other list.
// Once both of them go through reassigning,
// they will be equidistant from the collision point.
//
if (p1 == NULL) p1 = headB;
if (p2 == NULL) p2 = headA;
}

return p1;
}

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
2
3
4
5
6
7
8
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *cur1 = headA, *cur2 = headB;
while(cur1 != cur2){
cur1 = cur1?cur1->next:headB;
cur2 = cur2?cur2->next:headA;
}
return cur1;
}

python


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

Concise python code with comments

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
# @param two ListNodes
# @return the intersected ListNode
def getIntersectionNode(self, headA, headB):
if headA is None or headB is None:
return None

pa = headA # 2 pointers
pb = headB

while pa is not pb:
# if either pointer hits the end, switch head and continue the second traversal,
# if not hit the end, just move on to next
pa = headB if pa is None else pa.next
pb = headA if pb is None else pb.next

return pa # only 2 ways to get out of the loop, they meet or the both hit the end=None

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
if headA==None or headB==None:
return None
l1, l2 = headA, headB
while l1 and l2 and l1!=l2:
l1 = l1.next
l2 = l2.next
if l1==l2:
return l1
if l1==None:
l1=headB
if l2==None:
l2=headA
return l1

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//boundary check
if(headA == null || headB == null) return null;

ListNode a = headA;
ListNode b = headB;

//if a & b have different len, then we will stop the loop after second iteration
while( a != b){
//for the end of first iteration, we just reset the pointer to the head of another linkedlist
a = a == null? headB : a.next;
b = b == null? headA : b.next;
}

return a;
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = length(headA), lenB = length(headB);
// move headA and headB to the same start point
while (lenA > lenB) {
headA = headA.next;
lenA--;
}
while (lenA < lenB) {
headB = headB.next;
lenB--;
}
// find the intersection until end
while (headA != headB) {
headA = headA.next;
headB = headB.next;
}
return headA;
}

private int length(ListNode node) {
int length = 0;
while (node != null) {
node = node.next;
length++;
}
return length;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1=headA, p2=headB;
if(p1==null || p2==null) return null;
while(p1!=null && p2!=null && p1!=p2){
p1=p1.next;
p2=p2.next;
if(p1==p2) return p1;
if(p1==null) p1=headB;
if(p2==null) p2=headA;
}
return p1;
}
}

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)

1
2
3
4
5
6
7
8
9
10
11
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if( null==headA || null==headB )
return null;

ListNode curA = headA, curB = headB;
while( curA!=curB){
curA = curA==null?headB:curA.next;
curB = curB==null?headA:curB.next;
}
return curA;
}
谢谢你,可爱的朋友。