yxCoding

I am a coder

有序链表的两路合并

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

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

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct Node{
  5.         int value;
  6.         struct Node *next;
  7. };
  8.  
  9. struct Node *twoWay(struct Node *head1, struct Node *head2){
  10.         struct Node *p1=head1, *p2=head2, *nHead, *np;
  11.         np = nHead = (struct Node *)malloc(sizeof(struct Node));
  12.         while(p1!=NULL&&p2!=NULL){
  13.                 struct Node *tmp = (struct Node*) malloc(sizeof(struct Node));
  14.                 if(p1->value > p2->value){
  15.                         tmp->value = p2->value;
  16.                         tmp->next = NULL;
  17.                         np->next = tmp;
  18.                         np = tmp;
  19.                         p2 = p2->next;
  20.                 }else{
  21.                         tmp->value = p1->value;
  22.                         tmp->next = NULL;
  23.                         np->next = tmp;
  24.                         np = tmp;
  25.                         p1 = p1->next;
  26.                 }
  27.         }
  28.         if(p1==NULL){
  29.                 while(p2!=NULL){
  30.                         struct Node *tmp = (struct Node*) malloc(sizeof(struct Node));
  31.                         tmp->value = p2->value;
  32.                         tmp->next = NULL;
  33.                         np->next = tmp;
  34.                         np = tmp;
  35.                         p2 = p2->next;
  36.                 }
  37.         }else{
  38.                 while(p1!=NULL){
  39.                         struct Node *tmp = (struct Node*) malloc(sizeof(struct Node));
  40.                         tmp->value = p1->value;
  41.                         tmp->next = NULL;
  42.                         np->next = tmp;
  43.                         np = tmp;
  44.                         p1 = p1->next;
  45.                 }       
  46.         }
  47.         return nHead->next;
  48. }
  49.  
  50. struct Node *twoWay2(struct Node *p1, struct Node *p2){
  51.                 struct Node *nHead, *p;
  52.                 p =nHead = (struct Node *)malloc(sizeof(struct Node));
  53.                 while(p1!=NULL&&p2!=NULL){
  54.                         if(p1->value > p2->value){
  55.                                         p->next = p2;
  56.                                         p = p2;
  57.                                         p2 = p2->next;
  58.                         }else{
  59.                                         p->next = p1;
  60.                                         p = p1;
  61.                                         p1 = p1->next;
  62.                         }
  63.                 }
  64.                 if(p1==NULL)
  65.                         p->next = p2;
  66.                 else
  67.                         p->next = p1;
  68.                 return nHead->next;
  69. }
  70.  
  71. void printLink(struct Node *n){
  72.         while(n!=NULL){
  73.                 printf("%d ", n->value);
  74.                 n = n->next;
  75.         }
  76.         printf("\n");
  77. }
  78.  
  79. int main(int argc, char *argv[]){
  80.         int i;
  81.         struct Node p1[10], p2[10];
  82.         for(i=0; i<10; i++){
  83.                 p1[i].value = i*2;
  84.                 p1[i].next = (i+1)==10?NULL:&p1[i+1];
  85.                 p2[i].value = i*2 + 1;
  86.                 p2[i].next = (i+1)==10?NULL:&p2[i+1];
  87.         }
  88.         printLink(p1);
  89.         printLink(p2);
  90.         struct Node *p3 =       twoWay(p1,p2);
  91.         printLink(p3);
  92.        
  93.         printLink(p1);
  94.         printLink(p2);
  95.         p3 = twoWay2(p1, p2);
  96.         printLink(p3);
  97. }
  98.  

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


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter