Chinaunix

标题: 如何将两个链表的元素交叉并归？（不能申请额外的空间） [打印本页]

作者: 奔跑的猪 时间: 2005-01-06 16:37
标题: 如何将两个链表的元素交叉并归？（不能申请额外的空间）
头次在这里发帖，请这里的高手看看，有什么好点子？

有人说用那个“归并排序”？！不大明白，谁能给出些代码瞧瞧？

作者: 奔跑的猪 时间: 2005-01-06 16:38
标题: 如何将两个链表的元素交叉并归？（不能申请额外的空间）
或者用其它办法也行！有什么思路？

作者: 奔跑的猪 时间: 2005-01-06 17:07
标题: 如何将两个链表的元素交叉并归？（不能申请额外的空间）
斑竹，高手到哪里去了？？

作者: yuxh 时间: 2005-01-06 17:11
标题: 如何将两个链表的元素交叉并归？（不能申请额外的空间）
老了，看不懂题目的意思了。

作者: albcamus 时间: 2005-01-06 17:16
标题: 如何将两个链表的元素交叉并归？（不能申请额外的空间）
归并排序也要申请第三个list的空间，“不另外申请空间”的方法倘若有，偶拭目以待…………再说，链表又不支持随机访问，“排序”何为？

作者: 奔跑的猪 时间: 2005-01-06 17:23
标题: 如何将两个链表的元素交叉并归？（不能申请额外的空间）
不是啊！原题不可能出错的，既然它想考你这个！
题目就是这么简单！
我想假如两个链表是有序的，归并，可以理解为把一个链表的元素向两外一个插入，当然插入的结果是有序的！是不是这样？

作者: 奔跑的猪 时间: 2005-01-06 17:24
标题: 如何将两个链表的元素交叉并归？（不能申请额外的空间）
用C实现，不考虑C++！
有人能给出代码吗？
是否要用mergsort()?

作者: converse 时间: 2005-01-06 17:43
标题: 如何将两个链表的元素交叉并归？（不能申请额外的空间）
不能申请其它的空间应该指的是还是用的原来链表的空间吧

typedef type int;
typedef struct List
{
type data;
struct List *pNext;
}List, *pList;
/* 基本的思路是每个链表设置两个指针，一个存放当前结点，一个存放下一个结点，算法思路是把当前结点交替链接上 */
void Merge_List(pList s1, pList s2)
{
pList p1 = s1->;pNext, p2 = s2->;pNext;
assert(s1 && s2);
while (p1 && p2)
{
s1->;pNext = s2;
s2->;pNext = p1;
s1 = p1;
p1 = p1->;pNext;
s2 = p2;
p2 = p2->;pNext;
}
/* 把剩余的结点接上 */
s1->;pNext = (p1) ? p1 : p2;
}

复制代码

作者: 奔跑的猪 时间: 2005-01-06 18:40
标题: 如何将两个链表的元素交叉并归？（不能申请额外的空间）
恩，多谢楼上的，我已经自己写了一个！测试通过了！
你的没测，估计也应该没问题！

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)