大家好,又见面了,我是全栈君。
【题目】
输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是依照递增排序的。
【分析】
合并单链表,须要找到头结点,对照两个链表头结点后,确定头结点,再确定头结点下一个结点,循环递归的如前面一样操作确定每一个结点位置,同一时候考虑边界条件,假设两个链表为空。则肯定无需合并了,就是空链表,假设一个链表为空,还有一个不为空,则返回不为空的链表。详细分析流程能够看以下的样例:
【測试代码】
#include<stdio.h>
#include<stdlib.h>
#include<stack>
typedef int data_type;
typedef struct Node node_t;// 给struct Node取个别名node_t
typedef struct Node * node_ptr;//给struct Node*取个别名node_ptr
typedef struct Node
{
data_type data;
struct Node *node_next;//node_next是一个指向结构的指针,告诉指针要指向的地址就要付给它一个结构类型地址
};
//链表初始化
node_t * init()
{
node_ptr p;
p = (node_t *)malloc(sizeof(node_t));
p->node_next = NULL;
return p;
}
//在链表后面插入结点
node_t *insert_back(node_ptr p , data_type data)
{
node_ptr pnew = (node_t *)malloc(sizeof(node_t));
pnew ->node_next = NULL;
pnew ->data = data;
p->node_next = pnew;
return pnew;
}
node_t * merge(node_ptr list1_head, node_ptr list2_head)
{
if(list1_head == NULL)
return list2_head;
else if(list2_head == NULL)
return list1_head;
node_ptr merge_head = NULL;
if(list1_head ->data < list2_head->data)
{
merge_head = list1_head;
merge_head->node_next = merge(list1_head->node_next,list2_head);
}
else
{
merge_head = list2_head;
merge_head->node_next = merge(list1_head, list2_head->node_next);
}
return merge_head;
}
//正常打印
void print(node_ptr p)
{
if(!p)
{
printf("no data, you think too much");
return ;
}
node_ptr list = p;
while(list->node_next != NULL)
{
printf("%d ", list->data);
list = list->node_next;
}
printf("%d ",list->data);
printf("\n");
}
void main()
{
node_ptr pnode1,pnode2, list1,list2;
pnode1 = init();
pnode2 = init();
list1 = pnode1;
list2 = pnode2;
pnode1 = insert_back(pnode1, 1);
pnode1 = insert_back(pnode1, 3);
pnode1 = insert_back(pnode1, 5);
pnode2 = insert_back(pnode2 , 2);
pnode2 = insert_back(pnode2 , 4);
pnode2 = insert_back(pnode2 , 6);
printf("单链表1为:");
print(list1->node_next);
printf("其头结点元素为:%d\n", list1->node_next->data);
printf("单链表2为:");
print(list2->node_next);
printf("其头结点元素为:%d\n", list2->node_next->data);
printf("\n");
node_t *merge_list = merge(list1->node_next, list2->node_next);
printf("合并单链表顺序为:");
print(merge_list);
printf("头结点元素为:%d\n",merge_list->data);
printf("\n");
}
【输出】
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115853.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...