题目描述：输入两个链表，找出它们的第一个公共结点。
Solutions
第一反映是遍历一遍两个链表就可以了……
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
if pHead1 is None or pHead2 is None:
return None
ll_dict = {}
p1 = pHead1
while p1 is not None:
ll_dict[p1] = 1
p1 = p1.next
p2 = pHead2
while p2 is not None:
if p2 in ll_dict:
return p2
p2 = p2.next
return None
第二种方法是分析这种有公共结点的两个链表的形式，可以看出，从第一个公共结点开始后面的都是公共结点，那么我们从最后一个结点往前遍历到最后一个公共结点，即是原来顺序上的第一个公共结点，也就是图中从 7 遍历到 6。但是这里是单向链表不能往前遍历，于是我们想到这种访问顺序是栈的形式，那么同样遍历一遍两个链表利用栈存储，然后按照上面的思路找。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
if pHead1 is None or pHead2 is None:
return None
s1 = []
s2 = []
p1 = pHead1
while p1 is not None:
s1.append(p1)
p1 = p1.next
p2 = pHead2
while p2 is not None:
s2.append(p2)
p2 = p2.next
res = None
while len(s1) > 0 and len(s2) > 0:
top1 = s1.pop()
top2 = s2.pop()
if top1 == top2:
res = top1
else:
return res
return None
以上实现没有 AC，尚还没有找到问题所在。
第三种解法是先遍历得到两个链表的长度，然后然后在长的链表上先走对应的步骤就好了。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def length(self, pHead):
count = 0
p = pHead
while p is not None:
count += 1
p = p.next
return count
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
if pHead1 is None or pHead2 is None:
return None
count1 = self.length(pHead1)
count2 = self.length(pHead2)
if count1 > count2:
max_p, min_p = pHead1, pHead2
over_count = count1 - count2
else:
max_p, min_p = pHead2, pHead1
over_count = count2 - count1
for i in range(over_count):
max_p = max_p.next
while max_p is not None and min_p is not None:
if max_p == min_p:
return max_p
else:
max_p = max_p.next
min_p = min_p.next
return None
# 运行时间：44ms
# 占用内存：5756k