Merge Two Sorted Linked Lists

You are given two sorted linked lists. Your task is to merge these two lists into one sorted linked list.

The original lists are provided as space-separated integers on two separate lines. If a line is empty, it represents an empty list.

The underlying algorithm uses the following idea: maintain a dummy node and repeatedly append the smaller head between the two lists. Formally, if we denote the two lists by \(L_1\) and \(L_2\), the merged list \(L\) is given by:

\(L = merge(L_1, L_2)\)

where the merge procedure runs in \(O(n)\) time.

inputFormat

The input consists of two lines:

1. The first line contains a sequence of space-separated integers representing the first sorted list. An empty line represents an empty list.
2. The second line contains a sequence of space-separated integers representing the second sorted list. An empty line represents an empty list.

outputFormat

Output a single line containing the merged sorted list, with the integers separated by a single space.

1 3 5 7 9
2 4 6 8

1 2 3 4 5 6 7 8 9