合并两个有序单链表

在归并排序中，对顺序存储的且为升序的两个列表a和b进行合并,合并后的列表为c，实现如下：

/**
 * Merge two sorted src array a[] and b[] to dst array c[]
 */
void merge0(int c[],  size_t nc, int a[], size_t na, int b[], size_t nb)
{
        int i = 0; /* walk array a : read  */
        int j = 0; /* walk array b : read  */
        int k = 0; /* walk array c : write */

        while (i < na && j < nb) {
                int t = 0;

                if (a[i] < b[j]) {
                        t = a[i];    /* save a[i] to t */
                        i++;         /* move index of a[] forward */
                } else {
                        t = b[j];    /* save b[j] to t */
                        j++;         /* move index of b[] forward */
                }

                c[k] = t;            /* now save x to c[k] */
                k++;                 /* move index of c[] forward */
        }

        /* copy the left of a[] to c[] */
        while (i < na)
                c[k++] = a[i++];

        /* copy the left of b[] to c[] */
        while (j < nb)
                c[k++] = b[j++];
}

那么，如何合并两个有序的按升序排列的单链表呢？ 方法有三：

• 方法一: 将链表a和链表b的每一个结点的地址都dump出来，转化为顺序存储处理（设存入 A[]和B[]），然后使用上面的merge0()算法，设合并后的存储数组为C[], 最后将C[]的结点地址重新组织为一个单链表。这个方法的实现起来比较容易，但是时间复杂度和空间复杂度都比较高。
• 方法二: 使用链式插入排序，假设链表a的头结点的数据域较小，那么可以遍历链表b的每一个结点，将结点逐个插入到链表a中。这一方法实现起来不是很容易，因为链式插入排序的实现相对复杂。另外，这一方法的时间复杂度也不是很高。
• 方法三: 仿照顺序存储列表的合并方法对单链表a和b进行合并，时间复杂度很不错，只是实现起来不是很直观，也不是很容易。

方法一

static int
get_list_length(list_t *head)
{
        int len = 0;
        for (list_t *p = head; p != NULL; p = p->next)
                len++;
        return len;
}

static void
dump_list_node_addr(list_t *head, uintptr_t **saveto, int *saveto_sz)
{
        int len = get_list_length(head);

        uintptr_t *aux = (uintptr_t *)malloc(sizeof (uintptr_t) * len);
        if (aux == NULL) {
                *saveto = NULL;
                *saveto_sz = 0;
                return;
        }

        int index = 0;
        for (list_t *p = head; p != NULL; p = p->next)
                aux[index++] = (uintptr_t)p;

        *saveto = aux;
        *saveto_sz = len;
}

static void
merge0(uintptr_t *c, int nc, uintptr_t *a, int na, uintptr_t *b, int nb)
{
        int i = 0;
        int j = 0;
        int k = 0;

        while (i < na && j < nb) {
                if (((list_t *)a[i])->data < ((list_t *)b[j])->data)
                        c[k++] = a[i++];
                else
                        c[k++] = b[j++];
        }

        while (i < na)
                c[k++] = a[i++];

        while (j < nb)
                c[k++] = b[j++];
}

/**
 * Merge two sorted single linked lists (dst and src).
 */
list_t *
merge1(list_t *head1, list_t *head2)
{
        if (head1 == NULL)
                return head2;

        if (head2 == NULL)
                return head1;

        list_t *out = NULL;

        uintptr_t *a = NULL;
        uintptr_t *b = NULL;
        uintptr_t *c = NULL;
        int na = 0;
        int nb = 0;
        int nc = 0;

        /* 1. dump the address of per node of list 1 to a[] */
        dump_list_node_addr(head1, &a, &na);
        if (a == NULL)
                goto done;

        /* 2. dump the address of per node of list 2 to a[] */
        dump_list_node_addr(head2, &b, &nb);
        if (b == NULL)
                goto done;

        /* 3. alloc memory for c[] */
        nc = na + nb;
        c = (uintptr_t *)malloc(sizeof (uintptr_t) * nc);
        if (c == NULL)
                goto done;
        memset(c, 0, nc);

        /* 4. merge a[] and b[] to c[] */
        merge0(c, nc, a, na, b, nb);

        /* 5. rebuild dst single linked list according to c[] */
        for (int i = 0; i < nc - 1; i++)
                ((list_t *)c[i])->next = (list_t *)c[i+1];
        ((list_t *)c[nc-1])->next = NULL;
        out = (list_t *)c[0];

done:
        if (c != NULL) free(c);
        if (b != NULL) free(b);
        if (a != NULL) free(a);

        return out;
}

在上面的方法中，假设链表a的长度为na, 链表b的长度为nb, 一个指针的大小为8个字节(64位处理器上)，那么我们使用的辅助存储为 8 * (na + nb) * 2。而时间复杂度，大约是O(4*(na+nb))。方法虽然比较笨，但是要写出上面的代码，需要对指针的本质有深刻的理解。

方法二

/**
 * Insertion Sort on a Single Linked List : insert a node to the sorted list
 */
static void
list_insert(list_t **head, list_t *node)
{
        if (*head == NULL) {
                *head = node;
                return;
        }

        /* get both prev and next of the node to insert */
        list_t *node_prev = *head;
        list_t *node_next = NULL;
        for (list_t *p = *head; p != NULL; p = p->next) {
                if (p->data <= node->data) {
                        node_prev = p;
                        continue;
                }

                node_next = p;
                break;
        }

        if (node_next == NULL) { /* append node to the tail */
                node_prev->next = node;
        } else {
                if (node_next == node_prev) { /* == *head */
                        node->next = *head;
                        *head = node;
                        return;
                }

                /* node_prev -> node -> node_next */
                node_prev->next = node;
                node->next = node_next;
        }
}

/**
 * Merge two sorted single linked lists (dst and src).
 */
list_t *
merge2(list_t *head1, list_t *head2)
{
        if (head1 == NULL)
                return head2;

        if (head2 == NULL)
                return head1;

        /* now merge the two lists */
        list_t *out = NULL;
        list_t *p = NULL;
        if (head1->data < head2->data) {
                out = head1;
                p = head2;
        } else {
                out = head2;
                p = head1;
        }

        /*
         * insert per node of list 'p' to the dst list one by one, and always
         * pick up the previous node inserted as the new head for getting good
         * time complexity once list_insert() is called
         */
        list_t *head = out;
        while (p != NULL) {
                list_t *this = p;
                p = p->next;
                this->next = NULL;
                list_insert(&head, this);
                head = this;
        }

        return out;
}

本方法最关键的是需要实现链式插入排序的核心函数list_insert()。 时间复杂度大约在O(na+nb)，但实现的主体函数merge2()非常容易理解。之所以说这个方法的时间效率还不够高，是因为是需要遍历开始结点数据域较大的那个链表的每一个结点。（对照方法三的实现，你就会发现此言不虚:-))

方法三

static void
list_insert_node_tail(list_t **head, list_t *tail, list_t *node)
{
        if (tail == NULL)
                *head = node;
        else
                tail->next = node;
}

list_t *
merge(list_t *head1, list_t *head2)
{
        list_t *out = NULL;
        list_t *tail = out;
        list_t *p1 = head1;
        list_t *p2 = head2;

        while (p1 != NULL && p2 != NULL) {
                list_t *node = NULL;

                if (p1->data < p2->data) {
                        node = p1;      /* 1. save p1 to node */
                        p1 = p1->next;  /* 2. move p1 forward */
                } else {
                        node = p2;      /* 1. save p2 to node */
                        p2 = p2->next;  /* 2. move p2 forward */
                }

                node->next = NULL;      /* 3. cut node's next off */
                                        /* 4. append node to out */
                list_insert_node_tail(&out, tail, node);
                tail = node;            /* 5. update the tail */
        }

        if (p1 != NULL) /* link the left of list 1 to the tail of out */
                list_insert_node_tail(&out, tail, p1);

        if (p2 != NULL) /* link the left of list 2 to the tail of out */
                list_insert_node_tail(&out, tail, p2);

        return out;
}

这才是一个高效的实现方法，因为时间复杂度为O(na+nb), 空间复杂度为O(1)。

小结： 链表操作体现的是工程师的编程功底，如果你在面试中遇到这样的问题，方法三通常是面试官所期待的。但是，实在没有办法在短时间内想明白的话，方法一和方法二也是可以的，至少表明你是有想法的程序员。完整代码实现戳这里。