Merge Two Sorted Singly Linked Lists

## Problem Merge two nondecreasing singly linked lists into one nondecreasing list by relinking their existing nodes. For portable input and output, the function receives the node values of each list as arrays and returns the values of the merged list; the intended algorithm must still follow the linked-list merge process and use `O(1)` auxiliary node storage. When two current node values are equal, take the node from the first list before the node from the second list. ### Function Contract Implement `mergeSortedLinkedLists(first, second)` and return an integer array. ### Constraints & Assumptions - `0 <= len(first), len(second)` and their combined length is at most `200,000`. - Each input is sorted in nondecreasing order. - Values are integers in the JavaScript-safe range `[-(2^53 - 1), 2^53 - 1]`, so their values and ordering are represented exactly in all four supported languages. - Duplicate values are allowed. - The array contract serializes the resulting linked-list traversal; do not solve by concatenating and sorting all values. ### Clarifying Questions to Ask - May nodes be reused? Yes; a real linked-list implementation should relink existing nodes. - How are equal values ordered? First-list nodes precede second-list nodes at an equal comparison. - Can either list be empty? Yes. - Is the target time linear in the total number of nodes? Yes. ```hint Maintain a tail pointer Compare the two current heads, append the smaller one to the result tail, and advance only the list from which that node came. ``` ### Examples - `first = [1, 2, 4]`, `second = [1, 3, 4]` returns `[1, 1, 2, 3, 4, 4]`. - `first = []`, `second = [0]` returns `[0]`. - Two empty lists return `[]`. ### Evaluation Focus - Advances the correct source pointer and appends the untouched remainder once one list is exhausted. - Preserves sorted order and the stated equal-value stability. - Runs in `O(n + m)` time and uses `O(1)` auxiliary linked-list storage beyond the returned serialization. ### Extensions to Discuss 1. How would you merge `k` sorted linked lists? 2. What changes if input nodes must not be mutated? 3. How could a cyclic input be detected before merging?