-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.py
More file actions
59 lines (49 loc) · 1.73 KB
/
Copy pathSolution.py
File metadata and controls
59 lines (49 loc) · 1.73 KB
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
nodeA = headA
nodeB = headB
lenA = self.getListLength(nodeA)
lenB = self.getListLength(nodeB)
if lenA > lenB:
headA = self.moveForward(lenA, lenB, headA)
else:
headB = self.moveForward(lenB, lenA, headB)
while headA is not None and headB is not None:
if headA == headB:
return headA
headA = headA.next
headB = headB.next
return None
def getListLength(self, head: ListNode) -> int:
length = 0
while head is not None:
head = head.next
length = length + 1
return length
def moveForward(self, longLength: int, shortLength: int, head: ListNode) -> ListNode:
delat = longLength - shortLength
while head is not None and delat > 0:
delat = delat - 1
head = head.next
return head
def getIntersectionNodeBySet(self, headA: ListNode, headB: ListNode) -> ListNode:
listNodeSet = set()
while headA is not None:
listNodeSet.add(headA)
headA = headA.next
while headB is not None:
if headB in listNodeSet:
return headB
headB = headB.next
return None
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
nodeA = headA
nodeB = headB
while nodeA != nodeB:
nodeA = nodeA.next if nodeA is not None else headB
nodeB = nodeB.next if nodeB is not None else headA
return nodeA