How do you merge two sorted linked lists?

You merge two sorted linked lists by creating a new list and appending the smallest elements from each list in order.

To merge two sorted linked lists, you need to create a new list that will hold the merged result. Start by initialising a new linked list, often referred to as a 'dummy' node. This node acts as the starting point of the new list. You also need two pointers, each pointing to the head of the two lists you want to merge.

The process of merging involves comparing the elements at the head of the two lists. You append the smaller element to the new list and move the pointer of that list to the next node. If the elements are equal, you can choose to append any of them and move the corresponding pointer. This process is repeated until you reach the end of one of the lists.

At this point, one list is exhausted while the other still has some elements. Since the lists are sorted, you can append the remaining elements from the non-exhausted list to the new list. The result is a new linked list that contains all the elements from the two lists in sorted order.

Here is a step-by-step guide on how to merge two sorted linked lists:

1. Initialise a new linked list (dummy node) and two pointers, each pointing to the head of the two lists.
2. Compare the elements at the head of the two lists.
3. Append the smaller element to the new list and move the pointer of that list to the next node.
4. If the elements are equal, append any of them and move the corresponding pointer.
5. Repeat steps 2-4 until you reach the end of one of the lists.
6. Append the remaining elements from the non-exhausted list to the new list.

Remember, the key to this process is that the original lists are sorted. This allows you to make the assumption that if an element is smaller than the heads of both lists, it will also be smaller than all the other elements in both lists.