tags:

views:

32

answers:

0
/*Task:
    Two ordered linklist contain number. eg.1->2->3-> and  2->3->5
    **Print** union of them eg.1->2->3->5 ,remove duplication, can't change 
    linklist

 Problem : 1. append() might need to be modified.
           2. dnot't know how to use append() to complete the task.

*/

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>

typedef struct lnode Lnode;
struct lnode {
  int data;
  Lnode *next;
};

Lnode * makeNode( int data )
{
   Lnode *new_node =(Lnode *)malloc( sizeof( Lnode ));
   if( new_node == NULL ) {
      fprintf(stderr,"Error: memory allocation failed.\n");
      exit( 1 );
   }
   new_node->data = data;
   new_node->next = NULL;
   return( new_node );
}

Lnode * get_list( void )
{ 
  Lnode *head = NULL;
  Lnode *new_node;
  Lnode *index_node;
  int ch;
  while((ch = getchar())!='\n'){
    new_node = makeNode(ch-48);
    if(head == NULL){
        head = new_node;
        index_node = head;
    }
    else {
        index_node->next = new_node;
        index_node = index_node->next;
    }
  }
  return( head );
}

void print(Lnode* head)
{
    Lnode* p = head->next;
    int t=1;
    printf("print:");
    do
    {    printf("%d",p->data);
        p=p->next;
        t++;
    }while(p);
}    

Lnode * append( Lnode *node, Lnode *head ){
  Lnode *new_node = head;
    if(head == NULL){
        return node;
    }
    if(node == NULL){
        return head;
    }
    while(new_node->next !=NULL){
        new_node = new_node->next;
    }
    new_node->next = node;
    new_node->next->next = NULL;
    return head;
}

Lnode* union_list(Lnode *list1,Lnode *list2)
{
    Lnode *list3,*head;
    head = list3 = (Lnode*)malloc(sizeof(Lnode));
    list3->next = NULL;
    while(list1 && list2){

        if(list1->data < list2->data){

            list1= append(list1,list3);
            list1 = list1->next;
        }
        else if(list1->data == list2->data){
            list3 = append(list1,list3);
            list1 = list1->next;
            list2 = list2->next;
        }
        else{
            list3 = append(list2,list3);
            list2 = list2->next;
        }
    }
    return list3;
}

void main()
{
    Lnode* head,*list1,*list2;
    printf("list1:");    
    list1 = get_list();
    printf("list2:");
    list2 = get_list();
    head = union_list(list1,list2);
    print(head);
    getchar();

}