Merge Two Price Feeds

Time Limit: 2sMemory: 256MB

Problem

Two market data providers each deliver a sorted stream of price quotes as a linked list. Your system needs to merge these two sorted streams into a single sorted linked list, preserving all quotes.

Given two sorted linked lists, merge them into one sorted list.

Input Format

Line 1: space-separated integers for the first sorted list (may be empty).
Line 2: space-separated integers for the second sorted list (may be empty).

Output Format

A single line of space-separated integers representing the merged sorted list.

Examples

Example 1

Input(Line 1: space-separated integers for the first sorted list (may be empty).)

1 3 5 7
2 4 6 8

Output

1 2 3 4 5 6 7 8

Merging [1,3,5,7] and [2,4,6,8] produces [1,2,3,4,5,6,7,8].

Example 2

Input(Line 1: space-separated integers for the first sorted list (may be empty).)

1 2 4
1 3 4

Output

1 1 2 3 4 4

Duplicates are preserved in sorted order.

Constraints

•0 ≤ list length ≤ 50
•-100 ≤ node value ≤ 100
•Both input lists are sorted in non-decreasing order

Loading interactive editor…