塞进裤子ヾ(≧O≦)〃嗷~

0%

剑指offer-52两个链表的第一个公共结点-python

《剑指offer》python实现系列,全目录

题目描述:

输入两个链表,找出它们的第一个公共结点。

第一想法:

a->b->c->d , h->b->c->d , 那么b是公共结点?

1
2
3
4
5
#暴力法 O(mn)
for i in listA:
for j in listB:
if i == j and i.next ==j.next:
return

剑指offer方法一:

有公共结点,因为是单链表,只有一个next,说明尾部是相同的。

可以从尾部开始往前比较。那么最后一个相同的结点就是第一个公共结点。

但单链表只能从前往后比较,先进后出

建立两个长度为m和n的辅助栈,mn分别是两个链表的长度。

剑指offer方法二:

不需要辅助空间

首先遍历两个链表得到它们的长度,就能知道哪个链表比较长,以及长的链表比短的链表多几个节点。

在第二次遍历的时候,在较长的链表上先走若干步,接着同时在两个链表上遍历,找到的第一个相同的节点就是它们的第一个公共节点。

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
30
31
32
33
34
# 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
length1,length2=0,0
cur1,cur2 = pHead1,pHead2
#计算两个链表的长度
while cur1 is not None:
length1 += 1
cur1 = cur1.next
while cur2 is not None:
length2 += 1
cur2 = cur2.next

#让长的链表先走
cur1,cur2 = pHead1,pHead2
if length2 > length1:
for i in range(length2-length1):
cur2 = cur.next
elif length1 > length2:
for i in range(length1-length2):
cur1 = cur1.next

while cur1 is not None:
if cur1 == cur2:
return cur1
cur1 = cur1.next
cur2 = cur2.next
return None

一次AC,好久没有过的感觉了

if help:小手一抖点个广告 or 大手一挥资助一下