Search⌘ K
Home
Courses
Coderust: Hacking the Coding Interview

Merge Two Sorted Linked Lists

Explore how to merge two sorted linked lists into one sorted linked list efficiently. Understand the step-by-step pointer manipulation and practice implementing this fundamental linked list algorithm. This lesson helps prepare you for coding interviews by teaching a common problem and solution with linear time complexity and constant space usage.

We'll cover the following...

Statement

We’re given two sorted linked lists. Merge them so that the resulting linked list is also sorted.

Example

Consider two sorted linked lists as an example:

g head1 head1 a 4 head1->a head2 head2 NULL NULL b 8 a->b c 15 b->c d 19 c->d e 22 d->e e->NULL a2 7 head2->a2 NULL2 NULL b2 9 a2->b2 c2 10 b2->c2 d2 16 c2->d2 d2->NULL2

The merged linked list should look like this:

g head1 head1 a 4 head1->a NULL NULL a2 7 a->a2 b 8 b2 9 b->b2 c 15 d2 16 c->d2 d 19 e 22 d->e e->NULL a2->b c2 10 b2->c2 c2->c d2->d

Sample input

[4, 8, 15, 19, 22]
[7, 9, 10, 16]

Expected output

[4, 7, 8, 9, 10, 15, 16, 19, 22]

Try it yourself

#include "LinkedList.cpp"
using namespace std;
typedef LinkedListNode* node_ptr;
node_ptr MergeSorted(node_ptr head1, node_ptr head2) {
	//TODO: Write - Your - Code
	return head1;
}

Solution

  • We maintain a head and a tail pointer on the merged linked list.
  • We choose the head of the merged linked list by comparing the first node of both linked lists.
  • For all subsequent nodes in both lists, we choose the smaller current node and link it to the tail of
...