87. Merge Lists

I'm a slow walker, but I never walk backwards.

Task Description

Write a program to merge two linked lists. The node of the list has two members -- a data value of type int, and a pointer next pointing to the next node. We assume that there will be no two nodes in the lists having the same data, and the two lists are sorted such that the data in them are in increasing order. Now you need to merge these two lists by reordering nodes in them so that that they appear as one sorted list. That is, when you are given two list (2, 4, 6, 9) and (1, 3, 10), the final list will be (1, 2, 3, 4, 6, 9, 10). The prototype of this function is as follows:

1
struct node *merge(struct node *list1, struct node *list2);

The two lists are list1 and list2. The head of the final list will be the return value of merge, and it will always be either list1 or list2. We assume that both list1 and list2 are not NULL, and they are both null terminated. Note that you need to sort the list by reordering only, so you are not allowed to declare array or use malloc().

node.h

1
2
3
4
5
6
7
8
9
10
11
#ifndef _NODE_H
#define _NODE_H
 
struct node {
    int value;
    struct node * next;
};
 
struct node * merge(struct node *, struct node *);
 
#endif

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#include <stdlib.h>
#include "node.h"
 
#define LEN 1000
 
struct node * build(int v[], int n) {
    struct node * head, * ptr;
    int i;
 
    if (!n)
        return 0;
 
    head = (struct node *) malloc(sizeof(struct node));
    ptr = head;
    head -> value = v[0];
    for (i = 1; i < n; i++) {
        ptr -> next = (struct node *) malloc(sizeof(struct node));
        ptr = ptr -> next;
        ptr -> value = v[i];
    }
    ptr -> next = 0;
    return head;
}
 
void print(struct node * ptr) {
    printf("%d", ptr -> value);
    if (ptr -> next) {
        putchar(' ');
        print(ptr -> next);
    }
}
 
int main() {
    int n1, n2;
    int v1[LEN], v2[LEN];
    int i;
    struct node * list1, * list2;
 
    scanf("%d", &n1);
    for (i = 0; i < n1; i++)
        scanf("%d", &v1[i]);
    scanf("%d", &n2);
    for (i = 0; i < n2; i++)
        scanf("%d", &v2[i]);
    list1 = build(v1, n1);
    list2 = build(v2, n2);
 
    print(merge(list1, list2));
    putchar('\n');
    return 0;
}

Hint

There is a very clean recursive solution for this problem. Consider the two heads of these two lists. Which node should appear first in the final answer ?

You can download node.h and main.c here, but remember you only need to submit the code of the merge function and the include tags needed (such as node.h).

Discussion