Combine Ordered Sequences

You are provided with the head nodes of two singly linked lists, sequence1 and sequence2, where both lists are arranged in ascending (non-decreasing) order.

Your task is to merge these two linked lists into a single unified linked list that preserves the ascending order. The resulting merged list should be constructed by interweaving the nodes from both original lists—you should reuse the existing nodes rather than creating new ones.

Return the head node of the newly combined linked list.

Understanding the Problem

A linked list is a linear data structure where each element (node) contains a value and a reference (pointer) to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations, which makes certain operations like insertion and deletion more efficient.

When merging two sorted linked lists, you need to compare the values at the current positions of both lists and select the smaller value to add to the result list. This process continues until all nodes from both lists have been processed.

Key Observations

1. Both input lists are already sorted in non-decreasing order, which means you can use a simple comparison-based merge strategy.

2. Either or both lists can be empty (null/None), and your solution should handle these edge cases gracefully.

3. The merge should be done in-place by rearranging the existing node pointers, not by creating a completely new list with copied values.

4. The relative order of equal elements should be preserved—if both lists have nodes with the same value, you can choose either one first, but maintaining stability (taking from the first list first) is a good practice.