Merge Two Sorted Linked Lists

Problem

Given two sorted linked lists list1 and list2, merge them into one sorted linked list and return the head of the merged list.

Example

Input

list1 = [1,2,4]
list2 = [1,3,4]

Output

[1,1,2,3,4,4]

Approach

Compare the first nodes of both lists.
Add the smaller node to the merged list.
Move the pointer of that list forward.
Continue until one list becomes empty.
Attach the remaining nodes.

Python Code
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

class Solution:
def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
dummy = ListNode(-1)
current = dummy
while list1 and list2:
if list1.val <= list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
if list1:
current.next = list1
elif list2:
current.next = list2
return dummy.next

Output
[1, 1, 2, 3, 4, 4]