列表

详情

MGJ11. 链表合并

描述

请编写一段代码，实现两个单向有序链表的合并

输入描述

第一行一个链表，如1 2 3 4 5

第二行一个链表，如2 3 4 5 6

输出描述

输出：1 2 2 3 3 4 4 5 5 6

示例1

输入: 

1 2 3 4 5
2 3 4 5 6

输出: 

1 2 2 3 3 4 4 5 5 6

原站题解

C 解法, 执行用时: 2ms, 内存消耗: 308KB, 提交时间: 2021-09-10 

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

typedef struct LST{
    int data;
    struct LST *next;
    
}list;

list *creat_list();
list *merge_list(list *p,list *q);
void print_list(list *p);

int main()
{
    int i;
    list *p,*q,*result;
    p=creat_list();
    q=creat_list();
    result = merge_list(p,q);
    print_list(result);
    
    return 0;
}

list *creat_list()
{
    list *head,*current,*last;
    head = current = last = (list*)malloc(sizeof(struct LST));
    while(1)
    {
        scanf("%d",&current->data);
        current->next = NULL;
        
        if(getchar() =='\n')
        {
            break;
        }
        last = (list *)malloc(sizeof(struct LST));
        current->next = last;
        current = last;
    }
    return head;
}

list *merge_list(list *p,list *q)
{
    list *p1,*q1;
    list *head,*current,*last;
    head = current = last = (list*)malloc(sizeof(struct LST));
    p1 = p;
    q1 = q;
    while(1)
    {
        if(p1->data < q1->data)
        {
            current->data = p1->data;
            p1 = p1->next;// p1为链表，头结点值被给出之后，要向后遍历
            if(p1==NULL)
            {
                current->next=q1;
                break;
            }
        }
        else
        {
            current->data = q1->data;
            q1 = q1->next;
            if(q1 == NULL)
            {
                current->next = p1;
                break;
            }
        }
        last = (list*)malloc(sizeof(struct LST));
        current->next = last;
        current = last;
        
    }
    return head;
}

void print_list(list *p)
{
    list *head = p;
    do{
        printf("%d ",head->data);
        head = head->next;
       }while(head);
}

C 解法, 执行用时: 2ms, 内存消耗: 332KB, 提交时间: 2021-09-10 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node{
	int elem;
	struct Node *next;
}SNode,*SLinketList;

#define NODESIZE sizeof(struct Node)

SLinketList slinket_list_create(void){
	struct Node* head = (struct Node*)malloc(NODESIZE);
	if(head==NULL){
		return NULL;
	}
	head->next = NULL;
	return head;
}

void slinket_list_insert_back(SLinketList head,int elem){
	struct Node *last = head;
	while(last->next!=NULL){
		last = last->next;
	}
	struct Node *node = (struct Node *)malloc(NODESIZE);
	node->elem = elem;
	node->next = NULL;
	last->next = node;
}

int slinket_list_size(SLinketList head){
	int size = 0;
	struct Node *node = head->next;
	while(node != NULL){
		size++;
		node = node->next;
	} 
	return size; 
}

void print(int num){
	printf("%d ",num);
}

void slinket_list_travel(SLinketList head,void (*travel)(int)){
	struct Node *node = head->next;
	while(node!=NULL){
		travel(node->elem);
		node = node->next;
	}
}

SLinketList Merge(SLinketList pHead1,SLinketList pHead2 ) {
    if(pHead1==NULL)
		return pHead2;
	if(pHead2==NULL)
		return pHead1;
    if(pHead1->next->elem>pHead2->next->elem)
    {
        SLinketList temp;
        temp=pHead1;
        pHead1=pHead2;
        pHead2=temp;
    }
    SLinketList curr1=pHead1->next;
    SLinketList curr2=pHead2->next;
	SLinketList aurr1=pHead1->next;
	SLinketList aurr2=pHead2->next;
	while(curr1!=NULL && curr2!=NULL)
	{
		if(curr1->elem<=curr2->elem)
		{
			aurr1=curr1;
			curr1=curr1->next;
		}
		else
		{
			aurr1->next=curr2;
			aurr1=curr2;
			aurr2=curr2->next;
			curr2->next=curr1;
			curr2=aurr2;
		}
	}
	if(curr1==NULL)
		aurr1->next=curr2;
	return pHead1;
}

int main()
{
    SLinketList list1=slinket_list_create();
    SLinketList list2=slinket_list_create();
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        slinket_list_insert_back(list1,n);
        if(getchar()=='\n')
            break;
    }
    while(scanf("%d",&n)!=EOF)
    {
        slinket_list_insert_back(list2,n);
    }
    list1=Merge(list1,list2);
    slinket_list_travel(list1,print);
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 344KB, 提交时间: 2020-06-08 

#include<stdio.h>
#include<stdlib.h>
typedef struct node {
    int val;
    struct node *next;
}linknode, *linklist;
void print_list(linklist p)
{
    while (p != NULL)
    {
        printf("%d ", p->val);
        p = p->next;
    }
}
linklist add_node(linklist p, int data)
{
    linklist t = (linklist)malloc(sizeof(linknode));
    t->val = data;
    t->next = NULL;
    
    if (p == NULL)
        return t;
    else
    {
        linklist r = p;
        while (r->next != NULL)
            r = r->next;
        r->next = t;
        return p;
    }
}
linklist merge_link(linklist p1,linklist p2)
{
    linklist FakeHead = (linklist)malloc(sizeof(linknode));
    FakeHead->next = p1;
    
    while (p2 != NULL)
    {
        linklist r = FakeHead;
        while ((r->next != NULL) && (r->next->val < p2->val))
            r = r->next;
        linklist tem = p2;
        p2 = p2->next;
        tem->next = r->next;
        r->next = tem;
    }
    return FakeHead->next;
}
int main()
{
    linklist head1 = NULL;
    linklist head2 = NULL;
    int num = 0;
    char ch;
    while ((scanf("%d%c", &num, &ch)>0))
    {
        head1 = add_node(head1, num);
        if (ch == '\n')
            break;
    }
    while ((scanf("%d%c", &num, &ch)>0))
    {
        head2 = add_node(head2, num);
        if (ch == '\n')
            break;
    }
    head1 = merge_link(head1,head2);
    print_list(head1);
    
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 352KB, 提交时间: 2020-05-20 

#include<stdio.h>
#include<stdlib.h>
typedef struct node {
    int val;
    struct node *next;
}linknode, *linklist;
void print_list(linklist p)
{
    while (p != NULL)
    {
        printf("%d ", p->val);
        p = p->next;
    }
}
linklist add_node(linklist p, int data)
{
    linklist t = (linklist)malloc(sizeof(linknode));
    t->val = data;
    t->next = NULL;
   
    if (p == NULL)
        return t;
    else
    {
        linklist r = p;
        while (r->next != NULL)
            r = r->next;
        r->next = t;
        return p;
    }
}
linklist merge_link(linklist p1,linklist p2)
{
    linklist FakeHead = (linklist)malloc(sizeof(linknode));
    FakeHead->next = p1;
   
    while (p2 != NULL)
    {
        linklist r = FakeHead;
        while ((r->next != NULL) && (r->next->val < p2->val))
            r = r->next;
        linklist tem = p2;
        p2 = p2->next;
        tem->next = r->next;
        r->next = tem;
    }
    return FakeHead->next;
}
int main()
{
    linklist head1 = NULL;
    linklist head2 = NULL;
    int num = 0;
    char ch;
    while ((scanf("%d%c", &num, &ch)>0))
    {
        head1 = add_node(head1, num);
        if (ch == '\n')
            break;
    }
    while ((scanf("%d%c", &num, &ch)>0))
    {
        head2 = add_node(head2, num);
        if (ch == '\n')
            break;
    }
    head1 = merge_link(head1,head2);
    print_list(head1);
   
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 364KB, 提交时间: 2020-05-03 

#include<stdio.h>
#include<stdlib.h>
typedef struct node {
    int val;
    struct node *next;
}linknode, *linklist;
void print_list(linklist p)
{
    while (p != NULL)
    {
        printf("%d ", p->val);
        p = p->next;
    }
}
linklist add_node(linklist p, int data)
{
    linklist t = (linklist)malloc(sizeof(linknode));
    t->val = data;
    t->next = NULL;
 
    if (p == NULL)
        return t;
    else
    {
        linklist r = p;
        while (r->next != NULL)
            r = r->next;
        r->next = t;
        return p;
    }
}
linklist merge_link(linklist p1,linklist p2)
{
    linklist FakeHead = (linklist)malloc(sizeof(linknode));
    FakeHead->next = p1;
 
    while (p2 != NULL)
    {
        linklist r = FakeHead;
        while ((r->next != NULL) && (r->next->val < p2->val))
            r = r->next;
        linklist tem = p2;
        p2 = p2->next;
        tem->next = r->next;
        r->next = tem;
    }
    return FakeHead->next;
}
int main()
{
    linklist head1 = NULL;
    linklist head2 = NULL;
    int num = 0;
    char ch;
    while ((scanf("%d%c", &num, &ch)>0))
    {
        head1 = add_node(head1, num);
        if (ch == '\n')
            break;
    }
    while ((scanf("%d%c", &num, &ch)>0))
    {
        head2 = add_node(head2, num);
        if (ch == '\n')
            break;
    }
    head1 = merge_link(head1,head2);
    print_list(head1);
 
    return 0;
}

上一题

© 2024 nowcoder.com