Merge Two Sorted Lists

Statement

Given the heads of two sorted linked lists, list1 and list2, merge these lists into a single sorted list. This involves integrating all the nodes from both lists while ensuring that their sorted order is preserved. Return the head of the merged linked list as the output.

Constraints:

• $0$ $\leq$ Number of nodes in both lists $\leq 50$

• $-100 \leq$ Node.data $\leq 100$

• Both lists are sorted in a non-decreasing order.

Examples