# Problem Description ## Merge Two Sorted Lists ### Overview Merge two sorted lists into a single sorted list. ### Problem Statement Given two sorted linked lists, merge them into a single sorted linked list. ### Rules and Constraints - The linked lists are represented as a series of nodes, each containing an integer value (`val`) and a reference to the next node in the list (`next`). - It is guaranteed that both input lists are sorted in ascending order. - The final output list should also be sorted in ascending order. - It is not required that the result be singly-linked; for example, it can be represented with a doubly-linked list, where each node not only points to the next node, but also to the previous one. - Time complexity should ideally be O(N+M), where N and M are the lengths of the two input lists. - Space complexity should ideally be O(N + M), as in the case of concatenation of the two lists. ### Input/Output Specifications Input: Two sorted linked lists. Output: A merged sorted linked list. ### Example **Input:** {"list1":[1,2,4],"list2":[1,3,4]} **Output:** [1,1,2,3,4,4]