6-4 两个有序链表序列的合并 (15 分)

### 回答1：
题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解题思路

我们可以使用递归的方法来解决这个问题。首先，我们比较两个链表的头节点，将较小的节点作为新链表的头节点。然后，我们将较小节点的 next 指针指向递归调用 mergeTwoLists 函数的结果。最后，我们返回新链表的头节点。

代码实现

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};

### 回答2：
题目描述:

给定两个单调递增的链表，将这两个链表合并为一个单调递增的链表，并且返回合并后的链表，你需要将其存在第一个链表中，第二个链表的头节点可以被修改。

思路分析:

创建一个新的链表和一个指针，分别指向这两个有序链表的头节点，然后比较这两个节点的大小，将较小的节点插入新链表中，同时将指针后移一位，再继续比较下一个节点，直到一个链表的全部节点都插入新链表中，此时，新链表后面没插入的元素一定都比插入的元素大，所以只需要将未插入的那个链表中剩余的元素都依次插入即可。

代码实现:

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==nullptr){
return l2;
}
if(l2==nullptr){
return l1;
}
ListNode* p1=l1;
ListNode* p2=l2;
ListNode* head;
if(p1->val<p2->val){
head=p1;
p1=p1->next;
}
else{
head=p2;
p2=p2->next;
}
ListNode* p=head;
while(p1&&p2){
if(p1->val<p2->val){
p->next=p1;
p1=p1->next;
}
else{
p->next=p2;
p2=p2->next;
}
p=p->next;
}
if(p1){
p->next=p1;
}
if(p2){
p->next=p2;
}
return head;
}

### 回答3：
本题要求合并两个有序链表。这个题目有很多方法可以做到，但是我们这里介绍一种比较简单的方法，用到了递归。

首先，我们要知道，如果两个链表都是空，则合并之后仍然是空链表；如果其中一个链表是空，合并之后的链表就是非空链表。因此，我们可以设置一个递归函数 merge(l1, l2) 来实现链表合并，其中 l1 和 l2 分别是需要合并的两个链表。

具体实现方法如下：

1. 如果 l1 为空，则返回 l2；如果 l2 为空，则返回 l1。

2. 如果 l1 的值小于等于 l2 的值，则将 l1 后面的链表和 l2 合并，并返回 l1。

3. 如果 l2 的值小于 l1 的值，则将 l2 后面的链表和 l1 合并，并返回 l2。

可以看出，这个递归函数的核心是比较 l1 和 l2 的值。如果 l1 的值小于等于 l2 的值，则说明应该把 l1 后面的链表和 l2 合并，然后返回 l1；如果 l2 的值小于 l1 的值，则说明应该把 l2 后面的链表和 l1 合并，然后返回 l2。这样不断递归下去，直到所有节点都被合并完毕，最后返回合并后的链表头。

这个方法的时间复杂度是 O(m+n)，其中 m 和 n 分别是两个链表的长度。这是因为每个节点只会被访问一次，而每次访问只需要 O(1) 的时间，因此总时间是两个链表长度的和。

综上所述，我们可以用递归函数 merge(l1, l2) 来实现两个有序链表的合并，时间复杂度为 O(m+n)。