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]