This is the most common interview question and most commonly required algorithm for writing any code.
Metaphor
Consider you are planning a trip in office and got 2 lists which has names listed on it in alphabetical order. You need to merge these two files to get a master participant list. Now, for this you can do a simple merge of the two lists to generate a single list.
Concept
For merging two lists is a most common algorithm required in many programs. Its similar to the merge algorithm over array where we split the list into 2 and merge. Here, we get 2 lists. We just merge them into a single list and return it.
Code
Using extra memory
1:
2: List* merge_lists(List *a1, List *a2)
3: {
4: List *c = 0;
5: while(a1 !=0 && a2!=0)
6: {
7: if(a1>data > a2>data)
8: {
9: if(c == 0)
10: c=createNode(a2>data);
11: else {
12: append(c, createNode(a2>data));
13: }
14:
15: a2 = a2>next;
16: }
17: else
18: {
19: if(c == 0)
20: c=createNode(a1>data);
21: else {
22: append(c, createNode(a1>data));
23: }
24:
25: a1 = a1>next;
26: }
27: }
28:
29: List *iter = c;
30: while(iter>next !=0) iter = iter>next;
31: if(a2 != 0)
32: iter>next = a2;
33: else
34: iter>next = a1;
35: return c;
36: }
37:
38: void main()
39: {
40: List *list1 = createNode(2);
41: append(list1, createNode(3));
42: append(list1, createNode(5));
43: append(list1, createNode(10));
44:
45: List *list2 = createNode(1);
46: append(list2, createNode(4));
47: append(list2, createNode(9));
48: append(list2, createNode(12));
49:
50: List *list3 = merge_lists(list1, list2);
51: }
There are interview questions like merge a1 and a2 and place it in a1 without using extra space. We will discuss about this tomorrow.
Important points

Merge algorithm onplace is very complex and mostly theoretical. We will concentrate on interview questions like How to sort 100GB worth of strings in the coming articles.

Note that the remaining list at the end is blindly appended to the new list.