-
Notifications
You must be signed in to change notification settings - Fork 0
/
merge_sorted_list.py
95 lines (75 loc) · 2.21 KB
/
merge_sorted_list.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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
'''
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 1
Output: [1]
Constraints:
The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
Follow up: Could you do this in one pass?
'''
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def linkedListString(head):
current_node = head
linked_list_str = '['
while current_node:
linked_list_str += str(current_node.val)
if current_node.next:
linked_list_str += ', '
current_node = current_node.next
linked_list_str += ']'
return linked_list_str
def mergeTwoListsHelper(node1, node2):
if node1 is None:
return node2
elif node2 is None:
return node1
else:
if node1.val <= node2.val:
merged_node = ListNode(node1.val)
merged_node.next = mergeTwoListsHelper(node1.next, node2)
else:
merged_node = ListNode(node2.val)
merged_node.next = mergeTwoListsHelper(node1, node2.next)
return merged_node
# Mege two lists recursively
def mergeTwoLists(list1, list2):
"""
:type list1: Optional[ListNode]
:type list2: Optional[ListNode]
:rtype: Optional[ListNode]
"""
return mergeTwoListsHelper(list1, list2)
# Some Test cases
if __name__ == "__main__":
node3 = ListNode(4)
node2 = ListNode(2, node3)
head1 = ListNode(1, node2)
node3 = ListNode(4)
node2 = ListNode(3, node3)
head2 = ListNode(1, node2)
head3 = head4 = None
head5 = None
head6 = ListNode(0)
# Examples
input = [
(head1, head2, [1,1,2,3,4,4]),
(head3, head4, []),
(head5, head6, [0])
]
for idx, (head1, head2, expected) in enumerate(input):
print("\nExample", idx, ":")
print("Input:", linkedListString(head1), linkedListString(head2))
print("Output:", linkedListString(mergeTwoLists(head1, head2)))
print("Expected:", expected)