「java合并链表」链表归并排序java
本篇文章给大家谈谈java合并链表，以及链表归并排序java对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
- 1、链表的合并
- 2、合并两个有序链表【递归、迭代】
- 3、使用java设计算法，完成将两个有序递增的单链表合并为一个有序递增的单链表，重复的元素只出现一次。
- 4、实现两个链表的合并
- 5、Java合并两个排序的链表问题（剑指offer）
- 6、如何把两个有序链表合并为一个有序链表(递增)？
链表的合并
#include "stdio.h"
struct student
{
int number;
int score;
struct student *next;
struct student *before; /*由于要排序，所以要建立双向链表 */
}*Head_A,*Rear_A,*Head_B,*Rear_B,*p,*p1;
void main()
{
int i,j,Length_A,Length_B,Length_Z;
printf("此程序是把a,b两个链表合并并按学号升序排列.\n");
printf("a,b两个链表中的结点包括学号、成绩。\n");
printf("先分别输入两个链表的长度.\n");
printf("请输入a链表的长度:"); /*输入链表a*/
scanf("%d",Length_A);
printf("请输入a链表结点中的学号和成绩\n");
printf(" 学号 成绩\n");
for(i=1;i=Length_A;i++)
{
p=(struct student*)malloc(sizeof(struct student));
printf("请输入第%d个同学的学号和成绩:",i);
scanf("%d%d",p-number,p-score);
p-next=NULL;
if(i==1) {Head_A=p;Rear_A=p;p-before=NULL;}
else {p-before=Rear_A;Rear_A-next=p;Rear_A=p;}
}
printf("现在将输出a链表.\n"); /*输出链表a*/
printf(" 学号 成绩\n");
p=Head_A;
for(i=1;i=Length_A;i++)
{
printf("第%d个同学:%d %d\n",i,p-number,p-score);
p=p-next;
}
printf("请输入b链表的长度:"); /*输入链表b*/
scanf("%d",Length_B);
printf("请输入b链表结点中的学号和成绩\n");
printf(" 学号 成绩\n");
for(i=1;i=Length_B;i++)
{
printf("第%d个同学的学号和成绩:",i);
scanf("%d%d",p-number,p-score);
p-next=NULL;
if(i==1) {Head_B=p;Rear_B=p;}
else {p-before=Rear_B;Rear_B-next=p;Rear_B=p;}
}
printf("现在将输出b链表.\n"); /*输出链表b*/
printf(" 学号 成绩\n");
p=Head_A;
for(i=1;i=Length_B;i++)
{
printf("第%d位同学的学号和成绩：%d %d\n",i,p-number,p-score);
p=p-next;
}
printf("现在将a,b链表进行合并\n"); /*合并两链表*/
Rear_A-next=Head_B; /*将b链表的头指针地址赋值给a链表的尾部*/
Rear_A=Head_B;
printf("现在输出合并后的新链表\n"); /*输出新链表*/
Length_Z=Length_A+Length_B; /*长度变为两链表之和*/
p=Head_A;
printf(" 学号 成绩\n");
for(i=1;i=Length_Z;i++)
{
printf("第%d位同学的学号和成绩:%d %d\n",i,p-number,p-score);
p=p-next;
}
p1=(struct student*)malloc(sizeof(struct student));
printf("现在进行排序工作\n");
for(i=1;iLength_Z;i++)
{ p=Head_A;
p-before=NULL;
p1=p-next;
for(j=1;j=Length_Z-i;j++)
{
if(p-numberp-next-number)
{
p1=p-next;
p-next=p1-next;
p1-next-before=p1-before;
p1-next=p1-before;
if(j==1) {p-before=p1;Head_A=p1;p1-before=NULL;}
else {p1-before=p-before;p1-before-next=p1;}
p1=p-next;
}
else {p=p1;p1=p1-next;}
}
}
/*经过上面的程序，已经把顺序排好*/
printf("现在将输出已按升序排列的新链表.\n");
printf(" 学号 成绩\n");
for(i=1;i=Length_Z;i++)
{
printf("第%d位同学的学号和成绩:%d %d\n",i,p-number,p-score);
p=p-next;
}
}
合并两个有序链表【递归、迭代】
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1-2-4, 1-3-4
输出：1-1-2-3-4-4
我们可以递归地定义在两个链表上进行合并（merge）操作的结果，如下所示（在不考虑空列表的情况下）：
也就是说，我们取两个列表头部中较小的那个，然后再加上合并其余元素所得到的结果。
我们直接对上述递归建模，首先考虑边界情况。 具体来说，如果 l1 或 l2 最初为 null，则不需要执行合并，我们只需返回非空列表。否则，我们需要确定 l1 和 l2 中哪个的头节点更小，并递归地处理该头节点的 next 值以得到下一次合并结果。 如果两个列表都以空结束，那么递归就会停止。
我们完全可以通过迭代实现相同的思想，假设 l1 完全小于 l2，并逐个处理元素，在 l1 的必要位置插入 l2 元素。
首先，设置一个 prehead 节点（虚节点），这会帮助我们轻松地返回合并之后的列表的头节点。 我们还需要维护一个 prev 指针，它指向可能需要调整 next 指针的当前节点。 然后，执行以下操作，直到 l1 和 l2 中至少有一个指向 null：如果 l1 处的值小于或等于 l2 处的值，那么我们将 l1 连接到前一个节点，并递增 l1。 否则，我们对 l2 做同样的事情。 不管我们连接的是哪个列表，我们都会增加 prev，使它总是保持比我们的表头落后一步。
循环终止后，l1 和 l2 中最多有一个是非空的。 因此（因为输入列表是按有序的），如果其中一个列表是非空的，那么它包含的元素一定大于所有先前合并的元素。 这意味着我们可以直接将非空列表连接到已合并列表并返回它。
使用java设计算法，完成将两个有序递增的单链表合并为一个有序递增的单链表，重复的元素只出现一次。
type
point=^node;
node=record
data:integer;
next:point;
end;
var h1,h2,h:point;
procedure prt(p:point); //打印链表
begin
p:=p^.next;
while pnil do
begin
write(p^.data,' ');
p:=p^.next;
end;
writeln;
end;
procedure creat(var h:point); //建立链表
var x:integer; p,q:^node;
begin
writeln('请输入升序的数，负数结束：');
new(h);
p:=h;
read(x);
while(x=0)do
begin
new(q);
q^.data:=x;
p^.next:=q;
p:=q;
read(x);
end;
p^.next:=nil;
end;
function merge_link(var p,q:point):point; //升序合并二个升序链表
var h,w:^node;
begin
w:=p; p:=p^.next; dispose(w); //回收一个头结点，p指向首个数据结点
w:=q; h:=q; q:=q^.next; //h:合并后的头结点，q指向首个数据结点
while (pnil)and(qnil) do //当二个链表都不空时
if(p^.dataq^.data) then //选一个小的结点
begin
w^.next:=p; //把小结点链入
p:=p^.next; //跳过此结点
w:=w^.next; //w指向当前合并后链表的尾结点
end
else
begin //下面三行作用同上
w^.next:=q;
q:=q^.next;
w:=w^.next;
end;
if pnil then w^.next:=p; //将未完的链表接入
if qnil then w^.next:=q; //将未完的链表接入
merge_link:=h; //返回合并后的链表头指针
end;
begin
creat(h1);
creat(h2);
h:=merge_link(h1,h2);
writeln('合并后的链表：');
prt(h);
实现两个链表的合并
#include stdio.h
#include malloc.h
int m, n;
int count = 1;
struct Node
{
int data;
struct Node *next;
}*A,*B,*C,*D;
//打印AList列表
void printList(struct Node *AList)
{
struct Node *post;
post = AList-next;
switch(count)
{
case 1:
printf("\nListA: ");
break;
case 2:
printf("\nListB: ");
break;
case 3:
printf("\nListC: ");
break;
case 4:
printf("\nListD: ");
break;
default:
printf("\nList: ");
break;
}
while (post)
{
printf("%d ",post-data);
post = post-next;
}
count ++;
}
//初始化表头,列表含有表头
void init()
{
A = (struct Node*)malloc(sizeof(struct Node));
A-data = 0;
A-next = 0;
B = (struct Node*)malloc(sizeof(struct Node));
B-data = 0;
B-next = 0;
C = (struct Node*)malloc(sizeof(struct Node));
C-data = 0;
C-next = 0;
D = (struct Node*)malloc(sizeof(struct Node));
D-data = 0;
D-next = 0;
}
//读取列表A和B
void ReadListAB()
{
int i;
struct Node *post;
struct Node *pre;
// 输入列表长度
printf("m="); scanf("%d",m);
printf("n="); scanf("%d",n);
//读取列表A
pre = A;
for(i=1; i=m; i++)
{
post = (struct Node*)malloc(sizeof(struct Node));
printf("A%d = ", i);
scanf("%d", post-data);
post-next = 0;
pre-next = post;
pre = post;
}
//读取列表B
pre = B;
for(i=1; i=n; i++)
{
post = (struct Node*)malloc(sizeof(struct Node));
printf("B%d = ", i);
scanf("%d", post-data);
post-next = 0;
pre-next = post;
pre = post;
}
}
//合并列表A和B
void MergeABToC()
{
int i;
struct Node *pre, *postA, *postB, *postC;
pre = C;
postA = A-next;
postB = B-next;
if(m = n)
{
for(i=1; i=n; i++)
{
postC = (struct Node*)malloc(sizeof(struct Node));
postC-data = postA-data;
postC-next = 0;
pre-next = postC;
pre = postC;
postC = (struct Node*)malloc(sizeof(struct Node));
postC-data = postB-data;
postC-next = 0;
pre-next = postC;
pre = postC;
postA = postA-next;
postB = postB-next;
}
for(i=n+1; i=m; i++)
{
postC = (struct Node*)malloc(sizeof(struct Node));
postC-data = postA-data;
postC-next = 0;
pre-next = postC;
pre = postC;
postA = postA-next;
}
}
else
{
for(i=1; i=m; i++)
{
postC = (struct Node*)malloc(sizeof(struct Node));
postC-data = postB-data;
postC-next = 0;
pre-next = postC;
pre = postC;
postC = (struct Node*)malloc(sizeof(struct Node));
postC-data = postA-data;
postC-next = 0;
pre-next = postC;
pre = postC;
postA = postA-next;
postB = postB-next;
}
for(i=m+1; i=n; i++)
{
postC = (struct Node*)malloc(sizeof(struct Node));
postC-data = postB-data;
postC-next = 0;
pre-next = postC;
pre = postC;
postB = postB-next;
}
}
}
//使用直接插入法，将C排序输出D
void SortCToD()
{
struct Node *pre, *postC, *postD, *lopD;
int len;
//表示总的长度
len = m + n;
pre = D; //指向D有序数列的尾指针
postC = C-next; //指向C列表
//列表D第一个节点加入
postD = (struct Node*)malloc(sizeof(struct Node));
postD-data = postC-data;
postD-next = 0;
pre-next = postD;
pre = postD;
postC = postC-next;
while (postC)
{
//pre为指向插入的前一个节点，lopD是指向插入的后一个节点
pre = D;
lopD = D-next;
while (lopD)
{
if (lopD-data postC-data)
break;
else
{
pre = lopD;
lopD = lopD-next;
}
}
//将节点插入
postD = (struct Node*)malloc(sizeof(struct Node));
postD-data = postC-data;
postD-next = 0;
pre-next = postD;
postD-next = lopD;
//循环条件
postC = postC-next;
}
}
void main(void)
{
init();
ReadListAB();
MergeABToC();
SortCToD();
printList(A);
printList(B);
printList(C);
printList(D);
}
以上代码可以运行，并且结果正确。
Java合并两个排序的链表问题（剑指offer）
1、先将两个链表分别进行各自排序。如果题目已说明原来的两个链表是已经排好序的话，此步可以省略。
2、新建一个空链表，按照顺序（或者由小到大或者由大到小），依次将两个链表的数据排列到新的链表中。
这样最后得到的链表就是最终合并的链表。
如何把两个有序链表合并为一个有序链表(递增)？
设链表结点结构为Node(int data, Node *next)，typedef Node List，链表均带表头结点。
思路是：把list1中的元素看成是集合1，把list2中的元素看成是集合2，把list1头结点（即list1结点）从集合1中脱离下来看成是目标集合的头结点，目标集合开始时是空集，并用last指针始终指向该集合的尾部，然后每次从集合1和集合2中取各自的第一个元素进行比较，较小者从相应集合里脱离，插入到目标集合list1的尾部即last的末尾，并将刚插入的元素作为目标集合list1的新的last，直到集合1为空或集合2为空时结束，最后将未空的集合中的剩余元素链接到last后面即可。
C语言是一种计算机程序设计语言，它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年推出，1978年后，C语言已先后被移植到大、中、小及微型机上，它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。
它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画，具体应用比如单片机以及嵌入式系统开发。
C语言继续发展，在1982年，很多有识之士和美国国家标准协会为了使这个语言健康地发展下去，决定成立C标准委员会，建立C语言的标准。委员会由硬件厂商，编译器及其他软件工具生产商，软件设计师，顾问，学术界人士，C语言作者和应用程序员组成。
关于java合并链表和链表归并排序java的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。