forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathintersection.py
More file actions
77 lines (58 loc) · 1.69 KB
/
intersection.py
File metadata and controls
77 lines (58 loc) · 1.69 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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
"""
Intersection of Two Linked Lists
Given two singly linked lists that converge at some node, find and return the
intersecting node. The node identity (not value) is the unique identifier.
Reference: https://leetcode.com/problems/intersection-of-two-linked-lists/
Complexity:
Time: O(m + n)
Space: O(1)
"""
from __future__ import annotations
class Node:
def __init__(self, val: object = None) -> None:
self.val = val
self.next: Node | None = None
def intersection(h1: Node, h2: Node) -> Node | None:
"""Find the intersection node of two linked lists.
Args:
h1: Head of the first linked list.
h2: Head of the second linked list.
Returns:
The intersecting node, or None if the lists do not intersect.
Examples:
>>> shared = Node(7)
>>> a = Node(1); a.next = shared
>>> b = Node(2); b.next = shared
>>> intersection(a, b).val
7
"""
count = 0
flag = None
h1_orig = h1
h2_orig = h2
while h1 or h2:
count += 1
if not flag and (h1.next is None or h2.next is None):
flag = (count, h1.next, h2.next)
if h1:
h1 = h1.next
if h2:
h2 = h2.next
long_len = count
short_len = flag[0]
if flag[1] is None:
shorter = h1_orig
longer = h2_orig
elif flag[2] is None:
shorter = h2_orig
longer = h1_orig
while longer and shorter:
while long_len > short_len:
longer = longer.next
long_len -= 1
if longer == shorter:
return longer
else:
longer = longer.next
shorter = shorter.next
return None