leetcode 【 Intersection of Two Linked Lists 】python 实现
题目：Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
代码：oj在线测试通过 Runtime: 1604 ms
1 # Definition for singly-linked list.
2 # class ListNode:
3 # def __init__(self, x):
4 # self.val = x
5 # self.next = None
6
7 class Solution:
8 # @param two ListNodes
9 # @return the intersected ListNode
10 def getListLen(self,head):
11 length = 0
12 while head is not None:
13 length += 1
14 head = head.next
15 return length
16
17 def getIntersectionNode(self, headA, headB):
18 if headA is None or headB is None:
19 return None
20
21 hA = headA
22 hB = headB
23
24 lenA = self.getListLen(hA)
25 lenB = self.getListLen(hB)
26
27 if lenA > lenB :
28 distance = lenA - lenB
29 for i in range(0,distance):
30 hA = hA.next
31 if lenA < lenB :
32 distance = lenB -lenA
33 for i in range(0,distance):
34 hB = hB.next
35
36 intersection = None
37 while hA is not None and hB is not None:
38 if hA == hB:
39 return hA
40 else:
41 hA = hA.next
42 hB = hB.next
43 return intersection
思路：
1. 首先要记录两个Linked List的长度
2. 双指针 分别指向两个List 指向长List的先走若干步,获得一个新的Linked List表头
3. 逐一比较两个List的每个指针的值是否相等：直到找到相等的，或者到None
页:
[1]