Merge Two Sorted Lists

Given the heads of two sorted linked lists, merge them into one sorted list and return its head.

Example

Input: 1 2 4 and 1 3 4 Output: 1 1 2 3 4 4

Approach

A dummy head node simplifies the edge case of "what's the very first node" — walk both lists with two pointers, always attaching the smaller current value to the result, advancing that list's pointer. Once one list is exhausted, attach the entire remainder of the other list at once (it's already sorted).

Input format

Line 1: first sorted list, space-separated Line 2: second sorted list, space-separated

Print the merged list, space-separated.