剑指offer之面试题17合并两个排序的链表

Love The Way You Lie 2022-08-22 03:49 95阅读 0赞

**问题描述**：

输入两个递增的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

**实现代码**如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    struct List{
    	int date;
    	struct List *next;
    };
    
    struct List* doMergeList(struct List *P1head,struct List *P2head){
    	if(P1head==NULL)
    		return P2head;
    	else if(P2head==NULL)
    		return P1head;
    	struct List *mergeHead = NULL;
    	if(P1head->date <P2head->date){
    		mergeHead = P1head;
    		mergeHead->next=doMergeList(P1head->next,P2head);
    	}else {
    		mergeHead=P2head;
    		mergeHead->next=doMergeList(P1head,P2head->next);
    	}
    	return mergeHead;
    }
    int main()
    {
    	struct List *P1head=(struct List *)malloc(sizeof(struct List));
    	struct List *P2head=(struct List *)malloc(sizeof(struct List));
    	P1head->date=0;P1head->next=NULL;
    	P2head->date=1;
    	P2head->next=NULL;
    	int i;
    	struct List *P1Temp=P1head,*P2Temp=P2head;
    	for(i=1;i<4;i++){
    		P1Temp->next=(struct List *)malloc(sizeof(struct List));
    		P1Temp->next->date=i;
    		P1Temp->next->next=NULL;
    		P2Temp->next=(struct List *)malloc(sizeof(struct List));
    		P2Temp->next->date=i*3;
    		P2Temp->next->next=NULL;
    		P1Temp=P1Temp->next;
    		P2Temp=P2Temp->next;
    	}
    	P1Temp=P1head,P2Temp=P2head;
    	printf("this is first list:\t");
    	while(P1Temp!=NULL){
    		printf("%d\t",P1Temp->date);
    		P1Temp=P1Temp->next;
    	}
    	printf("\nthis is second list:\t");
    	while(P2Temp!=NULL){
    		printf("%d\t",P2Temp->date);
    		P2Temp=P2Temp->next;
    	}
    	printf("\nthis is merge list:\t");
    	struct List *Head = doMergeList(P1head,P2head);
    	while(Head!=NULL){
    		printf("%d\t",Head->date);
    		Head=Head->next;
    	}
    	printf("\ndomerge done!\n");
    	return 0;
    }

**参考资料**：  
剑指offer  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51372134  
作者：WSYW126