数据结构

最强废铁h · 发表于 2021-10-10 15:07:03

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

设A和B是两个单链表，其表中元素递增有序，试设计一个算法，将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)。

monkey-D · 发表于 2021-10-10 16:24:40

本帖最后由 monkey-D 于 2021-10-10 16:28 编辑

两个链表分别倒序循环，每个指针的值比大小插入，辅助空间O(1)是要一个空指针完成插入操作，应该是这样，直接插入A链表里面多出来的空间不算辅助空间

桃花飞舞 · 发表于 2021-10-11 00:21:56

本帖最后由桃花飞舞于 2021-10-11 00:38 编辑

monkey-D 发表于 2021-10-10 16:24
两个链表分别倒序循环，每个指针的值比大小插入，辅助空间O(1)是要一个空指针完成插入操作，应该是这样，直 ...

可以新建两个链表，各自倒序循环也是可以，没有搞明白你，每个指针值比大小插入，辅助空间O（1）是要一个空指针完成插入操作，应该是这样，直接插入A链表里面多出来的空间不算辅助空间。的意思？这里有说把A和B归并成一个按元素值递减有序的单链表C。并要求辅助空间为O(1)说的的排序的算法不能用冒泡之类的意思吧。归并可以用归并排序呀。这个其实用数组也可以做吧，题目要用链表。可以先把A链表的值和B链表的值放到C链表，这个要怎么放入C链表是个疑问。这个主要是排序用哪种排法？或者怎么排序，倒序，正序倒没什么。

monkey-D · 发表于 2021-10-11 15:57:49

AB链表都是给条件有序的，一个个倒序下来就行

monkey-D · 发表于 2021-10-11 15:58:19

桃花飞舞发表于 2021-10-11 00:21
可以新建两个链表，各自倒序循环也是可以，没有搞明白你，每个指针值比大小插入，辅助空间O（1）是要一 ...

AB链表都是给条件有序的，一个个倒序下来就行

桃花飞舞 · 发表于 2021-10-11 21:56:05

monkey-D 发表于 2021-10-11 15:58
AB链表都是给条件有序的，一个个倒序下来就行

C链表是没顺序的所以要排序呀，主要就是怎么把A链表和B链表放入C链表，并且给C链表排序是关键

monkey-D · 发表于 2021-10-11 23:23:44

A有序B有序，把B的每个插入A不就变成一个有序的了？还需要排？再解释清楚点 A:1 3 5 6 7 B 2 4 6 8 10 把B插入A需要归并排序吗，取出B的每一个跟A比大小满足即插入变成1 2 3 4 5 6 7 8 9 10 清楚了吗
再开一个新的C链表辅助空间不就是C链表的大小，能是O(1)?

monkey-D · 发表于 2021-10-11 23:25:05

桃花飞舞发表于 2021-10-11 21:56
C链表是没顺序的所以要排序呀，主要就是怎么把A链表和B链表放入C链表，并且给C链表排序是关键

A有序B有序，把B的每个插入A不就变成一个有序的了？还需要排？再解释清楚点 A:1 3 5 6 7 B 2 4 6 8 10 把B插入A需要归并排序吗，取出B的每一个跟A比大小满足即插入A变成1 2 3 4 5 6 7 8 9 10 清楚了吗
再开一个新的C链表辅助空间不就是C链表的大小，能是O(1)?

桃花飞舞 · 发表于 2021-10-12 00:02:11

本帖最后由桃花飞舞于 2021-10-12 01:18 编辑

monkey-D 发表于 2021-10-11 23:25
A有序B有序，把B的每个插入A不就变成一个有序的了？还需要排？再解释清楚点 A:1 3 5 6 7 B 2 4 6 ...

可能你说的对，链表C不能建立，因为只要建立就可能遍历，辅助空间就不可能是O（1）了。不过把链表B插入链表A是个难点，毕竟插入时候由B链表传入A链表的参数是个结构体指针。而且A链表要向后挪一位

账号		自动登录	找回密码
密码			立即注册