# The first common node of the two linked lists

1, Title Description

Enter two acyclic single linked lists and find their first common node( Note: because the incoming data is a linked list, the prompt of error test data is displayed in other ways to ensure that the incoming data is correct)

Example 1
Input: {1,2,3}, {4,5}, {6,7}
Return value: {6,7}
Note: the first parameter {1,2,3} represents the non-public part of the first linked list, the second parameter {4,5} represents the non-public part of the second linked list, and the last {6,7} represents the public part of the two linked lists... These three parameters will finally be assembled into two two acyclic single linked lists with public nodes in the background

Example 2
Input: {1}, {2,3}, {}
Return value: {}
Note: the two linked lists have no public nodes, return null, and print {}

2, Problem solving ideas
(I)

Two intersecting linked lists are Y-shaped. You can start from the tail of two linked lists at the same time. The last same node is the first same node of the linked list. It can be realized by stack. The temporal complexity is O(m+n), and the spatial complexity is O(m+n)

```class Solution:
def FindFirstCommonNode(self , pHead1 , pHead2 ):
# write code here
while not pHead1 :
return None

stack1 = []
stack2 = []

first = None
while stack1 and stack2:
top1 = stack1.pop()
top2 = stack2.pop()
if top1 is top2:
first = top1
else:
break
return first
```

(2) Double stack

Press the elements in the linked list into the two stacks in turn, and then throw one element from the two stacks at a time until the thrown nodes are the same. The returned elements are public

```class Solution:
# write code here
lst1 = []
lst2 = []
result = []

return None

while p1:
lst1.append(p1)
p1 = p1.next
while p2:
lst2.append(p2)
p2 = p2.next

while lst1 and lst2:
node1 = lst1.pop()
node2 = lst2.pop()
if node1 == node2:
result.append(node1)

if result:
node = result.pop()
return node
```

(3) ifelse statement

No additional space is required to store the linked list. There is no need to know the length of the linked list in advance. Look at the following linked list example: 0-1-2-3-4-5-null a-b-4-5-null
The ifelse statement of the code, for a pointer p1, actually makes it run the linked list, and the length becomes the same.
If there is a common node, the part where the pointers go to the end together must overlap. Look at the path of the pointer below.
p1: 0-1-2-3-4-5-null (ifelse encountered at this time) - a-b-4-5-null
P2: a-b-4-5-null (ifelse encountered at this time) 0-1-2-3-4-5-null
Therefore, the length of the linked list to be traversed by the two pointers is the same!

```class Solution:
while p1!=p2:
p1 = p1.next if p1 else pHead2
p2 = p2.next if p2 else pHead1
return p1
```

Traverse the two linked lists respectively, save the nodes into two arrays, and then pop the two arrays respectively. If the first pair of different nodes is found, the previous node can be returned directly.

```class Solution:
listA, listB = [], []
return None
listA.reverse()
listB.reverse()
length = min(len(listB), len(listA))
temp=None
for i in range(length):
nodeA = listA.pop(0)
nodeB = listB.pop(0)
if nodeA == nodeB:
temp = nodeA
else:
break
return temp
```

Keywords: Python data structure linked list

Added by JennyG on Thu, 02 Sep 2021 00:09:12 +0300