Merge Two Sorted Linked Lists

If we are given two already sorted linked lists, how do we make them into one linked list while keeping the final linked list sorted as well? Let’s find out in this lesson.

Before getting started, we’ll make the following assumption:

Each of the sorted linked lists will contain at least one element.

A related problem is to create a third linked list which is also sorted. In this lesson, the two linked lists given will no longer be available in their original form, and only one linked list which includes both their nodes will remain. Let’s get started.

First of all, we’ll have a look at the algorithm which we’ll use to code and then we’ll analyze the implementation in Python.

Algorithm #

To solve this problem, we’ll use two pointers (p and q) which will each initially point to the head node of each linked list. There will be another pointer, s, that will point to the smaller value of data of the nodes that p and q are pointing to. Once s points to the smaller value of the data of nodes that p and q point to, p or q will move on to the next node in their respective linked list. If s and p point to the same node, p moves forward; otherwise q moves forward. The final merged linked list will be made from the nodes that s keeps pointing to. To get a clearer picture, let’s look at the illustration below: