有序链表的两路合并

yxjoey posted @ 2008年3月28日 06:15 in C语言 with tags c 程序 , 1858 阅读

将有序的两个链表合并成一个有序链表。下面的程序分别实现了修改原链表和不修改原链表的方法

#include <stdio.h>
#include <stdlib.h>
 
struct Node{
        int value;
        struct Node *next;
};
 
struct Node *twoWay(struct Node *head1, struct Node *head2){
        struct Node *p1=head1, *p2=head2, *nHead, *np;
        np = nHead = (struct Node *)malloc(sizeof(struct Node));
        while(p1!=NULL&&p2!=NULL){
                struct Node *tmp = (struct Node*) malloc(sizeof(struct Node));
                if(p1->value > p2->value){
                        tmp->value = p2->value;
                        tmp->next = NULL;
                        np->next = tmp;
                        np = tmp;
                        p2 = p2->next;
                }else{
                        tmp->value = p1->value;
                        tmp->next = NULL;
                        np->next = tmp;
                        np = tmp;
                        p1 = p1->next;
                }
        }
        if(p1==NULL){
                while(p2!=NULL){
                        struct Node *tmp = (struct Node*) malloc(sizeof(struct Node));
                        tmp->value = p2->value;
                        tmp->next = NULL;
                        np->next = tmp;
                        np = tmp;
                        p2 = p2->next;
                }
        }else{
                while(p1!=NULL){
                        struct Node *tmp = (struct Node*) malloc(sizeof(struct Node));
                        tmp->value = p1->value;
                        tmp->next = NULL;
                        np->next = tmp;
                        np = tmp;
                        p1 = p1->next;
                }       
        }
        return nHead->next;
}
 
struct Node *twoWay2(struct Node *p1, struct Node *p2){
                struct Node *nHead, *p;
                p =nHead = (struct Node *)malloc(sizeof(struct Node));
                while(p1!=NULL&&p2!=NULL){
                        if(p1->value > p2->value){
                                        p->next = p2;
                                        p = p2;
                                        p2 = p2->next;
                        }else{
                                        p->next = p1;
                                        p = p1;
                                        p1 = p1->next;
                        }
                }
                if(p1==NULL)
                        p->next = p2;
                else
                        p->next = p1;
                return nHead->next;
}
 
void printLink(struct Node *n){
        while(n!=NULL){
                printf("%d ", n->value);
                n = n->next;
        }
        printf("\n");
}
 
int main(int argc, char *argv[]){
        int i;
        struct Node p1[10], p2[10];
        for(i=0; i<10; i++){
                p1[i].value = i*2;
                p1[i].next = (i+1)==10?NULL:&p1[i+1];
                p2[i].value = i*2 + 1;
                p2[i].next = (i+1)==10?NULL:&p2[i+1];
        }
        printLink(p1);
        printLink(p2);
        struct Node *p3 =       twoWay(p1,p2);
        printLink(p3);
       
        printLink(p1);
        printLink(p2);
        p3 = twoWay2(p1, p2);
        printLink(p3);
}
 

最近要勤练基础编程知识了，对面试有用！(Bless me have a wonderful day tomorrow!!)

相关文章
全局相关文章

yxjoey

yxCoding

有序链表的两路合并

yxjoey

分类

标签云

最新评论

最新留言

友情链接

我的豆瓣收藏

浏览计数器