  Interview Questions

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.

## 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

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 |