-
Notifications
You must be signed in to change notification settings - Fork 0
/
MergeTwoSortedLists.py
47 lines (41 loc) · 1.73 KB
/
MergeTwoSortedLists.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
# pylint: disable=missing-module-docstring
# pylint: disable=missing-class-docstring
# pylint: disable=missing-function-docstring
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# Dummy node to point to the sorted list
head = ListNode()
# Temporary pointer which moves to next empty slot where we should add next
# node
pointer = head
# While either of lists are not empty
while list1 != None and list2 != None:
# If list1.val < list2.val, we add list1 node to pointer.next and
# we move list1 to next node
if list1.val < list2.val:
pointer.next = list1
list1 = list1.next
# If list2.val < list1.val, we add list2 node to pointer.next and
# we move list2 to next node
else:
pointer.next = list2
list2 = list2.next
# Moving pointer to next node
pointer = pointer.next
# If there are still some nodes in list1, that means we break out of loop
# because, list2 became empty, so we directly point pointer.next to list1
# which is the first node of remaining elements of list1
if list1 != None:
pointer.next = list1
# If there are still some nodes in list2, that means we break out of loop
# because, list1 became empty, so we directly point pointer.next to list2
# which is the first node of remaining elements of list2
if list2 != None:
pointer.next = list2
# Since, head node is a dummy node which points to sorted list, we return
# next node of head i.e; head.next
return head.next