欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PTA---6-3 链表拼接 (20分)

程序员文章站 2022-06-07 23:46:10
...

本题要求实现一个合并两个有序链表的简单函数。链表结点定义如下:

struct ListNode {
    int data;
    struct ListNode *next;
};

函数接口定义:

struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2);

其中list1list2是用户传入的两个按data升序链接的链表的头指针;函数mergelists将两个链表合并成一个按data升序链接的链表,并返回结果链表的头指针。

裁判测试程序样例:

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

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *createlist(); /*裁判实现,细节不表*/
struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2);
void printlist( struct ListNode *head )
{
     struct ListNode *p = head;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    struct ListNode  *list1, *list2;

    list1 = createlist();
    list2 = createlist();
    list1 = mergelists(list1, list2);
    printlist(list1);
	
    return 0;
}

/* 你的代码将被嵌在这里 */

 

输入样例:

1 3 5 7 -1
2 4 6 -1

 

输出样例:

1 2 3 4 5 6 7 

 

老规矩,先说思路。

旧的思路:我使用了双循环,用外循环在list2中行走,用内循环在list1中探索。不停地比较,直到将list1中的成分一个个拆分放进list2中。事实证明,那样相当繁琐。

新的思路:

初始状态(简单的案例)

PTA---6-3 链表拼接 (20分)

 p和q为两个指针,分别指向原list1和list2,即两个链表的头部。既然有list1和2为什么不直接用呢?因为一旦改变其数值可能就会造成丢失数据的结果。故定义了p和q。

 

接下来,将list1置为NULL,将他作为新的总链表的首部。

不断进行p指针位的data与q指针位data的比较,依题意,哪个比较小,就放在前面。即新的总链表加入该元素。

如图(红笔为总路径,蓝色为其中某一步的比较显示)

PTA---6-3 链表拼接 (20分)

直至参与的两个指针有一个为NULL了,无法比较了,就要停下来。然后你会想到,那还有另一指针没加上呢?对的,这里特殊处理补上就行啦。

 

 

下面附上源码:

struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2)
{
	struct ListNode *p=list1,*q=list2,*tail=NULL;  //新的表为list1~tail
	if(list1==NULL&&list2==NULL)    //初始的list1和2就都为空,极特殊的情况
	{
		return NULL;
	}
	list1=NULL;
	while(p!=NULL&&q!=NULL)    //有一个为空就停止了
	{
		if(p->data>q->data)    //哪个小就连哪个
		{
			if(list1==NULL)
			{
				list1 = q;
			}
			else
			{
				tail->next=q;
			}
			tail = q;
			q = q->next;
		}
		else
		{
			if(list1==NULL)
			{
				list1 = p;
			}
			else
			{
				tail->next=p;
			}
			tail = p;
			p = p->next;
		}
	}
	if(q==NULL)                //最后还要连上的剩余部分
	{
		tail->next = p;
	}
	if(p==NULL)
	{
		tail->next = q;
	}
	return list1;
}

 

相关标签: PTA错题