一、题目描述
输入两个无环的单链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
示例1
输入：{1,2,3},{4,5},{6,7}
返回值：{6,7}
说明：第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分…这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的
示例2
输入：{1},{2,3},{}
返回值：{}
说明：2个链表没有公共节点 ,返回null，后台打印{}
二、解题思路
（一）
两条相交的链表呈Y型。可以从两条链表尾部同时出发，最后一个相同的结点就是链表的第一个相同的结点。可以利用栈来实现。时间度有O(m+n), 空间复杂度为O(m + n)
class Solution:
def FindFirstCommonNode(self , pHead1 , pHead2 ):
# write code here
while not pHead1 :
return pHead1
while not pHead1:
return pHead2
if not pHead1 or not pHead2:
return None
stack1 = []
stack2 = []
while pHead1:
stack1.append(pHead1)
pHead1 = pHead1.next
while pHead2:
stack2.append(pHead2)
pHead2 = pHead2.next
first = None
while stack1 and stack2:
top1 = stack1.pop()
top2 = stack2.pop()
if top1 is top2:
first = top1
else:
break
return first
（二）双栈
依次将链表中的元素压入两个栈中，然后每次从两个栈中抛出一个元素，直到抛出的结点相同时返回后面的元素都是公共的
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
lst1 = []
lst2 = []
result = []
if not pHead1 or not pHead2:
return None
p1 = pHead1
p2 = pHead2
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
(三) ifelse语句
不需要存储链表的额外空间。也不需要提前知道链表的长度。看下面的链表例子： 0-1-2-3-4-5-null a-b-4-5-null
代码的ifelse语句，对于某个指针p1来说，其实就是让它跑了连接好的的链表，长度就变成一样了。
如果有公共结点，那么指针一起走到末尾的部分，也就一定会重叠。看看下面指针的路径吧。
p1：0-1-2-3-4-5-null(此时遇到ifelse)-a-b-4-5-null
p2: a-b-4-5-null(此时遇到ifelse)0-1-2-3-4-5-null
因此，两个指针所要遍历的链表就长度一样了！
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
p1,p2=pHead1,pHead2
while p1!=p2:
p1 = p1.next if p1 else pHead2
p2 = p2.next if p2 else pHead1
return p1
分别遍历两个链表，将节点保存到 两个数组中，再分别pop两个数组，如果找到第一对不相同的节点，那么直接返回上一个节点即可。
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
listA, listB = [], []
if not pHead2 and not pHead1:
return None
while pHead1:
listA.append(pHead1)
pHead1 = pHead1.next
while pHead2:
listB.append(pHead2)
pHead2 = pHead2.next
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
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/99759.html
