MGJ8. 链表合并
描述
请编写一段代码，实现两个单向有序链表的合并输入描述
第一行一个链表，如1 2 3 4 5输出描述
输出：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++14 解法, 执行用时: 2ms, 内存消耗: 236KB, 提交时间: 2019-12-04
#include<stdio.h>
int main(int argc, char **argv)
{
int i = 0, j,k,t, a[100];
for(j=0; j<2; j++)
{
while (scanf("%d", &a[i++]))
{
if (getchar() == '\n')break;
}
}
for (j = 0; j < i; j++)
{
for (k = j + 1; k < i;k++)
{
if (a[j]>a[k])
{
t = a[j];
a[j] = a[k];
a[k] = t;
}
}
}
for (j = 0; j < i; j++)
{
printf("%d ",a[j]);
}
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 296KB, 提交时间: 2021-12-12
#include <stdio.h>
struct Node {
int val;
struct Node *next;
};
struct Node* createBuff() {
struct Node* head = NULL;
struct Node** p = &(head);
while(1){
struct Node *node = malloc(sizeof(struct Node));
node->next = NULL;
scanf("%d",&node->val);
*p = node;
p = &node->next;
if (getchar() == '\n')break;
}
return head;
}
int main() {
struct Node *pHead1 = createBuff();
struct Node *pHead2 = createBuff();
while(pHead1 && pHead2){
if(pHead1->val > pHead2->val){
printf("%d ", pHead2->val);
pHead2 = pHead2->next;
}else{
printf("%d ", pHead1->val);
pHead1 = pHead1->next;
}
}
if(pHead1){
while(pHead1){
printf("%d ", pHead1->val);
pHead1 = pHead1->next;
}
}else{
while(pHead2){
printf("%d ", pHead2->val);
pHead2 = pHead2->next;
}
}
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 296KB, 提交时间: 2021-11-18
#include <stdio.h>
struct Node {
int val;
struct Node *next;
};
struct Node* parseBuff(char* buff) {
int i = 0;
struct Node* head = NULL;
struct Node* p = NULL;
while(buff[i] != '\0') {
char temp[32];
int j = 0;
while( buff[i] == ' ' ) {
i++;
}
while( buff[i] != '\0' && buff[i] != ' ' ) {
temp[j++] = buff[i++];
}
if( j > 0 ) {
temp[j++] = '\0';
struct Node *node = malloc(sizeof(struct Node));
node->next = NULL;
node->val = atoi(temp);
if( head == NULL ) {
head = p = node;
} else {
p->next = node;
p = node;
}
}
}
return head;
}
int main() {
char buff[4096];
gets(buff);
struct Node *head1 = parseBuff(buff);
gets(buff);
struct Node *head2 = parseBuff(buff);
// struct Node *head = NULL;
while( head1 != NULL || head2 != NULL ) {
if( head1 == NULL ) {
while( head2 != NULL ) {
if( head2->next == NULL ) {
printf("%d\n", head2->val);
} else {
printf("%d ", head2->val);
}
head2 = head2->next;
}
break;
}
if( head2 == NULL ) {
while( head1 != NULL ) {
if( head1->next == NULL ) {
printf("%d\n", head1->val);
} else {
printf("%d ", head1->val);
}
head1 = head1->next;
}
break;
}
if( head1->val < head2->val ) {
printf("%d ", head1->val);
head1 = head1->next;
continue;
}
printf("%d ", head2->val);
head2 = head2->next;
}
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 320KB, 提交时间: 2021-07-31
#include <stdio.h>
typedef struct List
{
int num;
struct List *Next;
}list;
list *creat_LIST();
list *compare_LIST(list *p,list *q);
void print_LIST(list *p);
int main()
{
int i;
list *p,*q,*result;
p=creat_LIST();
// printf("hello");
q=creat_LIST();
// print_LIST(p);
// print_LIST(q);
result=compare_LIST(p,q);
print_LIST(result);
return 0;
}
list *creat_LIST()
{
list *head,*current,*node;
head=current=node=(list *)malloc(sizeof(list));
while(1)
{
scanf("%d",¤t->num);
current->Next=NULL;
if(getchar()=='\n')
break;
node=(list *)malloc(sizeof(list));
current->Next=node;
current=node;
}
return head;
}
list *compare_LIST(list *p,list *q)
{
list *head,*current,*node,*q1,*p1;
p1=p;
q1=q;
head=current=node=(list *)malloc(sizeof(list));
while(1)
{
if(p1->num<q1->num)
{
current->num=p1->num;
p1=p1->Next;
if(p1==NULL)
{
current->Next=q1;
break;
}
}
else
{
current->num=q1->num;
q1=q1->Next;
if(q1==NULL)
{
current->Next=p1;
break;
}
}
node=(list*)malloc(sizeof(list));
current->Next=node;
current=node;
}
return head;
}
void print_LIST(list *p)
{
list *head=p;
do
{
printf("%d ",head->num);
head=head->Next;
}while(head);
}
C 解法, 执行用时: 2ms, 内存消耗: 328KB, 提交时间: 2021-10-30
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node*pnext;
};
void Inite(struct Node* plist)
{
assert(plist!=NULL);
plist->pnext=NULL;
}
struct Node* BuyNode(int val)
{
struct Node*p=(struct Node*)malloc(sizeof(struct Node));
assert(p!=NULL);
p->data=val;
p->pnext=NULL;
return p;
}
void Insert(struct Node* plist,int val)
{
struct Node*p=plist;
while(p->pnext!=NULL)
{
p=p->pnext;
}
p->pnext=BuyNode(val);
}
struct Node* combinsort(struct Node* plist1,struct Node* plist2)
{
// struct Node*p=plist1;
// while(p->pnext!=NULL)
// {
// p=p->pnext;
// }
// p->pnext=plist2->pnext;
// int tmp=0;
// int i=0;
// for(struct Node*n=plist1->pnext;n!=NULL;n=n->pnext)
// {
// i++;
// }
// for(int j=0;j<i;j++)
// {
// for(struct Node*q=plist1->pnext;q->pnext!=NULL;q=q->pnext)
// {
// if(q->data > q->pnext->data)
// {
// tmp=q->pnext->data;
// q->pnext->data=q->data;
// q->data=tmp;
// }
// }
// }
// return plist1;
// }
struct Node*p=plist1;
struct Node*q=plist2->pnext;
for(q=plist2->pnext;q!=NULL;q=plist2->pnext)//下行循环，数据开始
{
for(p=plist1;p->pnext!=NULL;p=p->pnext)//上行循环找位置，头节点开始
{//q找到第一个比它大,
if((p->pnext->data) > (q->data))
{
break;
}
}//绑在他的前面
plist2->pnext=q->pnext;//把q踢出
q->pnext=p->pnext;
p->pnext=q;
}
return plist1;
}
void show(struct Node* plist)
{
struct Node*p=plist->pnext;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->pnext;
}
}
int main()
{
struct Node plist1;
struct Node plist2;
Inite(&plist1);
Inite(&plist2);
int j=0;
for(int i=0;i<7;i++)
{
scanf("%d",&j);
Insert(&plist1,j);
if(getchar()=='\n')
{
break;
}
}
for(int i=0;i<7;i++)
{
scanf("%d",&j);
Insert(&plist2,j);
if(getchar()=='\n')
{
break;
}
}
// int arr[7]={-1,-1,-1,-1,-1,-1,-1};
// int brr[7]={-1,-1,-1,-1,-1,-1,-1};
// int i;
// for(i=0;i<7;i++)
// {
// scanf("%d",&arr[i]);
// if(getchar()=='\n')
// {
// break;
// }
// }
// for(i=0;i<7;i++)
// {
// scanf("%d",&brr[i]);
// if(getchar()=='\n')
// {
// break;
// }
// }
// int m=0;
// int n=0;
// while(arr[m]!=-1)
// {
// m++;
// }
// while(brr[n]!=-1)
// {
// n++;
// }
// for(i=0;i<m;i++)
// {
// Insert(&plist1,arr[i]);
// }
// for(i=0;i<n;i++)
// {
// Insert(&plist2,brr[i]);
// }
//show(&plist1);
//printf("\n");
//show(&plist2);
struct Node*p=combinsort(&plist1,&plist2);
show(p);
return 0;
}