  Interview Questions

Merge two sorted linked lists
This is a common interview question testing basic knowledge of linked lists. The goal here is merge two linked lists that are already sorted.
For example: if L1 = 1 -> 3 -> 10 and L2 = 5 -> 6 -> 9 then your program should output the linked list 1 -> 3 -> 5 -> 6 -> 9 -> 10.

## Algorithm

The algorithm for this question is quite simple since the two linked lists are already sorted. We create a new linked list and loop through both lists appending the smaller nodes. We'll be using some code that we used in a previous linked list interview question.
(1) Create a new head pointer to an empty linked list. (2) Check the first value of both linked lists. (3) Whichever node from L1 or L2 is smaller, append it to the new list and move the pointer to the next node. (4) Continue this process until you reach the end of a linked list.

## Example

L1 = 1 -> 3 -> 10 L2 = 5 -> 6 -> 9 L3 = null Compare the first two nodes in both linked lists: (1, 5), 1 is smaller so add it to the new linked list and move the pointer in L1. L1 = 3 -> 10 L2 = 5 -> 6 -> 9 L3 = 1 Compare the first two nodes in both linked lists: (3, 5), 3 is smaller so add it to the new linked list and move the pointer in L1. L1 = 10 L2 = 5 -> 6 -> 9 L3 = 1 -> 3 Compare the first two nodes in both linked lists: (10, 5), 5 is smaller so add it to the new linked list and move the pointer in L2. L1 = 10 L2 = 6 -> 9 L3 = 1 -> 3 -> 5 Compare the first two nodes in both linked lists: (10, 6), 6 is smaller so add it to the new linked list and move the pointer in L2. L1 = 10 L2 = 9 L3 = 1 -> 3 -> 5 -> 6 Compare the first two nodes in both linked lists: (10, 9), 9 is smaller so add it to the new linked list and move the pointer in L2. L1 = 10 L2 = null L3 = 1 -> 3 -> 5 -> 6 -> 9 Because L2 points to null, simply append the rest of the nodes from L1 and we have our merged linked list. L3 = 1 -> 3 -> 5 -> 6 -> 9 -> 10

## Code

```function Node(data, next) {
this.data = data;
this.next = next;
}

function merge(L1, L2) {

// create new linked list pointer
var L3 = new Node(null, null);
var prev = L3;

// while both linked lists are not empty
while (L1 !== null && L2 !== null) {
if (L1.data <= L2.data) {
prev.next = L1;
L1 = L1.next;
} else {
prev.next = L2;
L2 = L2.next;
}
prev = prev.next;
}

// once we reach end of a linked list, append the other
// list because we know it is already sorted
if (L1 === null) { prev.next = L2; }
if (L2 === null) { prev.next = L1; }

// return the sorted linked list
return L3.next;

}

// create first linked list: 1 -> 3 -> 10
var n3 = new Node(10, null);
var n2 = new Node(3, n3);
var n1 = new Node(1, n2);
var L1 = n1;

// create second linked list: 5 -> 6 -> 9
var n6 = new Node(9, null);
var n5 = new Node(6, n6);
var n4 = new Node(5, n5);
var L2 = n4;

merge(L1, L2);
```
```class Node:
def __init__(self, data, next):
self.data = data
self.next = next

def merge(L1, L2):

# create new linked list pointer
L3 = Node(None, None)
prev = L3

# while both linked lists are not empty
while L1 != None and L2 != None:
if L1.data <= L2.data:
prev.next = L1
L1 = L1.next
else:
prev.next = L2
L2 = L2.next
prev = prev.next

# once we reach end of a linked list, append the other
# list because we know it is already sorted
if L1 == None:
prev.next = L2
elif L2 == None:
prev.next = L1

return L3.next

# create first linked list: 1 -> 3 -> 10
n3 = Node(10, None)
n2 = Node(3, n3)
n1 = Node(1, n2)
L1 = n1

# create second linked list: 5 -> 6 -> 9
n6 = Node(9, None)
n5 = Node(6, n6)
n4 = Node(5, n5)
L2 = n4

# print the linked list
merged = merge(L1, L2)
while merged != None:
print str(merged.data) + ' -> '
merged = merged.next
print 'None'
```

## Running time

This algorithm runs in O(n + m) time where n and m are the lengths of the respective linked lists. This is the running time because to merge both linked lists into one, we need to iterate through each node in the list.

## Sources

http://www.careercup.com/question?id=5187906612232192 http://www.careercup.com/question?id=2394668 mrdaniel published this on 11/24/15 |
Comments
• +
• 1
• -
• Hi, sort of new to programming, I understand the solution. However, why does the console only shows until n5, and then object? I would was thinking it would show something like this {data: 1, next: { data: 3, next: { data: 5, next:{data:6, next:{data:9, next:{data:10, next:null}}}} } } Thanks!
• +
• 1
• -
• @crp2002, It does this simply because JavaScript doesn't want to print out every single object that is within an object that is within an object etc... so it stops at the fourth level. If you run the code in your console then you should be able to show the contents of that object!
• +
• -1
• -
• When I tried running this on LeetCode, the provided code printed one list then another list (each unsorted) into a third list.
Log in to submit a comment.