面试题 17

1 题目描述

合并两个有序链表

2 解法描述

链表合并过程如下：从合并两个链表的首结点开始，两个链表中的值较小的首节点最为合并后链表的首节点，两个链表剩余的节点依然是排序的，合并步骤和之前合并首节点是一致的，是典型的递归过程。

3 c 语言实现

#include<stdio.h>
typedef int ElemType;
typedef struct node{
    ElemType data;
    struct node* next;
}LNode,*LinkList;
void createList_tail(LinkList *L){
    ElemType temp;
    LNode* p,*r;
    scanf("%d",&temp);
    while(temp != -1){
        p=(LinkList) malloc (sizeof(LNode));
        p->data = temp;
        p->next=NULL;
        if(*L==NULL){
           *L=p;
        }else{
            r->next=p;
        }
        r=p;
        scanf("%d",&temp);
    }
}
void showList(LinkList L){
    LinkList temp = L;
    while(temp!= NULL){
        printf("%d ",temp->data);
        temp = temp->next;
    }
}
LNode* merge(LNode* l1,LNode* l2){
    if(l1==NULL) return l2;
    if(l2==NULL) return l1;
    LNode* node;
    if(l1->data<=l2->data){
        node=l1;
        node->next=merge(l1->next,l2);
    }else{
        node=l2;
        node->next=merge(l1,l2->next);
    }
    return node;
}
void main(){
    LinkList L1=NULL;
    createList_tail(&L1);
    showList(L1);
    printf("\n");
    LinkList L2=NULL;
    createList_tail(&L2);
    showList(L2);
    printf("\n");
    LinkList mergeList=merge(L1,L2);
    showList(mergeList);
}