现在的位置: 首页 > 综合 > 正文

将两个有序链表合并为一个有序链表

2018年03月16日 ⁄ 综合 ⁄ 共 2701字 ⁄ 字号 评论关闭
struct link_node{
    int data ;
    struct link_node *next ;
} ;
struct link_node *create_linklist(int arr[],int len) {
    assert(arr!=NULL) ;
    struct link_node *p_head = (struct link_node*)malloc(
                        sizeof(struct link_node)) ;
    struct link_node *p_tmp = p_head ;
    for(int i=0 ; i<len ; i++){
        p_tmp->next = (struct link_node*)malloc(
                    sizeof(struct link_node)) ;
        p_tmp->next->data = arr[i] ;
        p_tmp = p_tmp->next ;
    }
    p_tmp->next = NULL ;
    return p_head ;
}
void print_linklist(struct link_node *p_head){
    assert(p_head!=NULL) ;
    struct link_node *p_tmp = p_head->next ;
    while(p_tmp!=NULL){
        cout<<p_tmp->data<<"," ;
        p_tmp = p_tmp->next ;
    }
    cout<<endl ;
}
int judge_reverse(struct link_node *p_head){
    assert(p_head!=NULL &&
           p_head->next!=NULL &&
           p_head->next->next!=NULL) ;
    return p_head->next->data>p_head->next->next->data ;
}
struct link_node * bubble_sort(struct link_node *p_head){
    assert(p_head!=NULL) ;
    struct link_node *p_tmp = p_head ;
    struct link_node *p_tail = NULL ;
    struct link_node *p_index = p_head ;
    /*note: termination condition*/
    while(p_tail!=p_head->next&&p_tail!=p_head->next->next){
        p_index = p_head ;
        while(p_index->next != p_tail &&
              p_index->next->next != p_tail){
            if(p_index->next->data > p_index->next->next->data){
                p_tmp = p_index->next ;
                p_index->next = p_tmp->next ;

                p_tmp->next = p_index->next->next ;
                p_index->next->next = p_tmp ;
            }
            p_index = p_index->next ;
        }
        p_tail = p_index->next ;
    }
    return p_head ;
}
struct link_node *merge_linklist(struct link_node *p_head1,
                                 struct link_node *p_head2){
    assert(p_head1!=NULL && p_head2!=NULL) ;
    struct link_node *p_tmp = NULL ;
    struct link_node *p_list1 = NULL ;
    struct link_node *p_list2 = NULL ;

    p_list1 = p_head1->next->data<p_head2->next->data?p_head1:p_head2 ;
    p_list2 = p_head1->next->data<p_head2->next->data?p_head2:p_head1 ;

    while(p_list1->next!=NULL && p_list2->next!=NULL){

        if(p_list1->next->data>p_list2->next->data){
            /*remove the smaller node from list2*/
            p_tmp = p_list2->next ;
            p_list2->next = p_tmp->next ;
            /*insert the node into list1*/
            p_tmp->next = p_list1->next ;
            p_list1->next = p_tmp ;
        }
        p_list1=p_list1->next ;
    }
    if(p_list1->next==NULL && p_list2->next!=NULL){
        p_list1->next = p_list2->next ;
    }
    return p_head1->next==NULL?p_head2:p_head1 ;
}
int count_linklist(struct link_node *const p_head){
    assert(p_head!=NULL) ;
    int count = 0 ;
    struct link_node *p_tmp = p_head->next ;
    while(p_tmp!=NULL){
        count++ ;
        p_tmp = p_tmp->next ;
    }
    return count ;
}
int main()
{
    int arr1[]={20,12,31,34,42,24,46} ;
    int arr2[]={2,4,3,78,1,51,9,432,5,7,8,11,32,20,12,24,31,21} ;

    struct link_node *p_head1 = create_linklist(arr1,sizeof(arr1)/sizeof(arr1[0])) ;
    p_head1 = bubble_sort(p_head1) ;
    print_linklist(p_head1) ;
    struct link_node *p_head2 = create_linklist(arr2,sizeof(arr2)/sizeof(arr2[0])) ;
    p_head2= bubble_sort(p_head2) ;
    print_linklist(p_head2) ;

    struct link_node *p_tmp = merge_linklist(p_head1,p_head2) ;
    print_linklist(p_tmp) ;

    cout<<"sizeof(arr1)="<<sizeof(arr1)/4<<endl ;
    cout<<"sizeof(arr2)="<<sizeof(arr2)/4<<endl ;
    cout<<"sizeof(merge)="<<count_linklist(p_tmp)<<endl ;
}

抱歉!评论已关闭.