-
Notifications
You must be signed in to change notification settings - Fork 0
/
zipper_lists.py
55 lines (47 loc) · 1.24 KB
/
zipper_lists.py
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
class Node:
def __init__(self, val):
self.val = val
self.next = None
# O(min(n, m)) Time | O(1) Space
def zipper_lists(head_1, head_2):
tail = head_1
current_h1 = head_1.next
current_h2 = head_2
count = 0
while current_h1 is not None and current_h2 is not None:
if count % 2 == 0:
tail.next = current_h2
current_h2 = current_h2.next
else:
tail.next = current_h1
current_h1 = current_h1.next
tail = tail.next
count += 1
if current_h1 is not None:
tail.next = current_h1
if current_h2 is not None:
tail.next = current_h2
return head_1
# O(min(n, m)) Time | O(min(n, m)) Space
# def zipper_lists(head_1, head_2):
# if head_1 is None and head_2 is None:
# return None
# if head_1 is None:
# return head_2
# if head_2 is None:
# return head_1
# next_1 = head_1.next
# next_2 = head_2.next
# head_1.next = head_2
# head_2.next = zipper_lists(next_1, next_2)
# return head_1
# a -> b -> c
# h1 n1
# x -> y -> z
# h2 n2
# a -> x -> result of zipper_lists(next_1, next_2)
# b -> c
# h1 n1
# y -> z
# h2 n2
# a -> x -> b -> y ... returning to the parent