The problem is as follows:

You are given the heads of two sorted linked lists `list1`

and `list2`

.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

```
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
```

Example 2:

```
Input: list1 = [], list2 = []
Output: []
```

Example 3:

```
Input: list1 = [], list2 = [0]
Output: [0]
```

Here is how I solved it:

Let's go through the provided definition for a singly-linked list:

```
class ListNode:
def __init__(self, val=0, next=None):
# Data stored in node val
self.val = val
# Reference to the next node
self.next = next
```

A singly linked list is a linear data structure where elements are connected in a sequence, and each element points to the next one using a pointer.

With that said, let's step through the logic here.

- Initialize a dummy_node that represents the starting point for the new merges sorted list.
- Set it to a pointer current_node (address in RAM, aka a variable) to construct the new list. Initially, this pointer will point to the dummy node.

```
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy_node = ListNode()
current_node = dummy_node
```

- Use a while loop to iterate through both lists at the same time until of them is null.
- Choose the head with the smaller value of the two lists: if value of current node in
`list1`

is less than value of node in`list2`

, then append the`list1`

node to the merged list and move to next node in`list1`

. - Else, append the
`list2`

node to merged list and move to next node in`list2`

. - We are still in the while loop. Move the current_node pointer to the newly added node

```
while list1 and list2:
if list1.val < list2.val:
current_node.next = list1
list1 = list1.next
else:
current_node.next = list2
list2 = list2.next
current_node = current_node.next
```

- After the while loop, if there are remaining nodes in
`list1`

or`list2`

, append them to the merged list. - Return the head of the merged list, which is the next node of the dummy node.

```
if list1:
current_node.next = list1
else:
current_node.next = list2
return dummy_node.next
```

Here is the completed solution:

```
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy_node = ListNode()
current_node = dummy_node
while list1 and list2:
if list1.val < list2.val:
current_node.next = list1
list1 = list1.next
else:
current_node.next = list2
list2 = list2.next
current_node = current_node.next
if list1:
current_node.next = list1
else:
current_node.next = list2
return dummy_node.next
```

## Top comments (0)