如何将两个链表的元素交叉并归？（不能申请额外的空间）

奔跑的猪

头次在这里发帖，请这里的高手看看，有什么好点子？

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

奔跑的猪

或者用其它办法也行！有什么思路？

奔跑的猪

斑竹，高手到哪里去了？？

yuxh

老了，看不懂题目的意思了。

albcamus

归并排序也要申请第三个list的空间，“不另外申请空间”的方法倘若有，偶拭目以待…………再说，链表又不支持随机访问，“排序”何为？

奔跑的猪

不是啊！原题不可能出错的，既然它想考你这个！
题目就是这么简单！
我想假如两个链表是有序的，归并，可以理解为把一个链表的元素向两外一个插入，当然插入的结果是有序的！是不是这样？

奔跑的猪

用C实现，不考虑C++！
有人能给出代码吗？
是否要用mergsort()?

converse

不能申请其它的空间应该指的是还是用的原来链表的空间吧

1. 
   
2. typedef type int;
   
3. 
   
4. typedef struct List
   
5. {
   
6.          type data;
   
7.          struct List *pNext;
   
8. }List, *pList;
   
9. /* 基本的思路是每个链表设置两个指针，一个存放当前结点，一个存放下一个结点，算法思路是把当前结点交替链接上 */
   
10. void Merge_List(pList s1, pList s2)
    
11. {
    
12.          pList p1 = s1->;pNext, p2 = s2->;pNext;
    
13.          assert(s1 && s2);
    
14. 
    
15.          while (p1 && p2)
    
16.          {
    
17.                   s1->;pNext = s2;               
    
18.                   s2->;pNext = p1;
    
19.                   s1 = p1;
    
20.                   p1 = p1->;pNext;
    
21.                   s2 = p2;
    
22.                   p2 = p2->;pNext;
    
23.          }
    
24.          /* 把剩余的结点接上 */
    
25.          s1->;pNext = (p1) ? p1 : p2;
    
26. 
    
27. }
    
28.          

复制代码

奔跑的猪

恩，多谢楼上的，我已经自己写了一个！测试通过了！
你的没测，估计也应该没问题！