Coderust: Hacking the Coding Interview/

...

/

Merge Two Sorted Linked Lists

Merge Two Sorted Linked Lists

Given two sorted linked lists, merge them so that the resulting linked list is also sorted.

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

main.cpp
LinkedList.cpp
LinkedListNode.cpp
#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
...