题目描述:
输入两个链表,找出它们的第一个公共结点。
【思路】
两个链表成Y字形,故只需将长的链表先走多余的长度,再两个链表同时走,求出相应的公共节点即可
【代码】
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
def list_len(node):
l = 0
while node!=None:
l+=1
node = node.next
return l
p1_len = list_len(pHead1)
p2_len = list_len(pHead2)
if p1_len > p2_len:
pLong = pHead1
pShort = pHead2
gap_len = p1_len-p2_len
else:
pLong = pHead2
pShort = pHead1
gap_len = p2_len-p1_len
#让长链表先走
for i in range(gap_len):
pLong=pLong.next
#寻找最先的公共节点
while pLong!=None and pShort!=None:
if pLong==pShort:
return pLong
else:
pLong = pLong.next
pShort = pShort.next