c++中合并两个有序链表的方法
导读：本文共2689字符，通常情况下阅读需要9分钟。同时您也可以点击右侧朗读，来听本文内容。按键盘←（左） →（右） 方向键可以翻页。
摘要： 1.题目要求这是一道求职面试时经常要求手写或者机试的经典题目。已知两个链表head1和head2各自有序，请把它们合并成一个链表依然有序。结果链表要包含head1和head2的所有节点，即使节点值相同。注意：不能开辟新空间来存储合并后的链表。如果第一次做该题，很容易会想到使用新链表来存储合并后的有序链表。虽然可以如此实现，但是不符合常规解法和面试官的要求。2.非... ...
目录
(为您整理了一些要点),点击可以直达。
1.题目要求
这是一道求职面试时经常要求手写或者机试的经典题目。
已知两个链表head1和head2各自有序，请把它们合并成一个链表依然有序。结果链表要包含head1和head2的所有节点，即使节点值相同。
注意：不能开辟新空间来存储合并后的链表。如果第一次做该题，很容易会想到使用新链表来存储合并后的有序链表。虽然可以如此实现，但是不符合常规解法和面试官的要求。
2.非递归实现
算法过程：
输入：两个有序的单链表head1与head2；
输出：合并后的有序单链表mergeHead；
算法描述：
（1）如果head1或head2为空链表，则直接返回另外一个链表；
（2）选择head1与head2链表当前节点值较小的节点，挂接到后并后的链表mergeHead；
（3）重复步骤2，直到链表head1或者head2遍历完成，未遍历完的链表，直接挂接到mergeHead的尾节点。
具体实现如下：
运行程序，输出结果：
从小到大顺序输入链表1：
1 2 3 5
ss0 strIn:1 2 3 5
从小到大顺序输入链表2：
3 4 5 6 7 8
ss1 strIn:3 4 5 6 7 8
合并后链表：
1 2 3 3 4 5 5 6 7 8
3.递归实现
从上面合并两个有序链表的步骤中可以看出，每次合并的步骤（2）都是一样的，由此我们想到了递归。具体实现如下：
c++中合并两个有序链表的方法的详细内容，希望对您有所帮助，信息来源于网络。