《剑指offer》python实现系列,全目录
题目描述:
输入两个链表,找出它们的第一个公共结点。
第一想法:
a->b->c->d , h->b->c->d , 那么b是公共结点?
1 2 3 4 5
| 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 Solution: def FindFirstCommonNode(self, pHead1, pHead2): 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,好久没有过的感觉了