将两个递增单链表合并成一个递增单链表

可以使用归并排序的思想，从头开始比较两个链表的节点大小，将较小的节点加入新链表中，直到其中一个链表为空，然后将另一个链表剩余的节点加入新链表中即可。以下是示例代码：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    cur->next = l1 ? l1 : l2;
    return dummy->next;
}

其中，ListNode 是单链表的节点结构体，包含一个整数 val 和一个指向下一个节点的指针 next。dummy 是一个虚拟节点，用于简化代码。

相关问题

用c++写一个两个递增单链表合并成一个递增单链表

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
int val;
struct ListNode *next;
};

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
struct ListNode *head = NULL;
struct ListNode *tail = NULL;
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
if (head == NULL) {
head = l1;
tail = l1;
} else {
tail->next = l1;
tail = tail->next;
}
l1 = l1->next;
} else {
if (head == NULL) {
head = l2;
tail = l2;
} else {
tail->next = l2;
tail = tail->next;
}
l2 = l2->next;
}
}
if (l1 != NULL) {
tail->next = l1;
}
if (l2 != NULL) {
tail->next = l2;
}
return head;
}

int main() {
// 构造链表1
struct ListNode *l1 = (struct ListNode*)malloc(sizeof(struct ListNode));
l1->val = 1;
l1->next = (struct ListNode*)malloc(sizeof(struct ListNode));
l1->next->val = 3;
l1->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
l1->next->next->val = 5;
l1->next->next->next = NULL;

// 构造链表2
struct ListNode *l2 = (struct ListNode*)malloc(sizeof(struct ListNode));
l2->val = 2;
l2->next = (struct ListNode*)malloc(sizeof(struct ListNode));
l2->next->val = 4;
l2->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
l2->next->next->val = 6;
l2->next->next->next = NULL;

// 合并链表
struct ListNode *merged = mergeTwoLists(l1, l2);

// 输出合并后的链表
while (merged != NULL) {
printf("%d ", merged->val);
merged = merged->next;
}
printf("\n");

return 0;
}

将两个递增的单链表合并成一个递增的单链表

### 回答1：

可以使用合并两个排序链表的方法来将两个递增的单链表合并成一个递增的单链表。首先分别定义两个指针来指向两个链表的头结点，然后比较指针指向的节点值，将值较小的节点添加到新链表中，并将指针指向下一个节点，直到两个指针均到达链表尾部。

### 回答2：
算法步骤如下：
1. 首先，创建一个新的单链表，用来存放合并后的链表。
2. 定义两个指针p和q分别指向两个递增单链表的头节点。
3. 比较p和q指针所指节点的值，将较小值的节点添加到新的单链表中，并将指针向后移动一位。
4. 当其中一个链表遍历结束时，将另一个链表剩余的节点添加到新的单链表中。
5. 返回新的单链表即为合并后的递增单链表。

具体实现如下所示：

# 定义节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    # 创建一个dummy节点作为新链表的头节点
    dummy = ListNode(0)
    p = l1
    q = l2
    current = dummy
    
    # 循环比较两个链表的节点值，并将较小值的节点添加到新链表中
    while p and q:
        if p.val < q.val:
            current.next = p
            p = p.next
        else:
            current.next = q
            q = q.next
        current = current.next
    
    # 将剩余的节点添加到新链表中
    if p:
        current.next = p
    if q:
        current.next = q
    
    # 返回新链表中去掉dummy节点后的头节点
    return dummy.next

时间复杂度：合并两个链表需要遍历所有节点，时间复杂度为O(m + n)，其中m和n分别为两个链表的长度。

空间复杂度：只使用了常数级别的额外空间，空间复杂度为O(1)。

### 回答3：
将两个递增的单链表合并成一个递增的单链表的方法是，首先定义一个新的单链表，然后分别定义两个指针，分别指向两个原始链表的头结点。通过比较两个指针所指节点的值，将值较小的节点加入到新的链表中，并将指针指向下一个节点。重复这个过程，直到其中一个链表为空。然后将另一个非空链表剩余的节点直接添加到新的链表的末尾。

具体实现如下：
1. 创建一个新链表，定义一个头指针和一个当前指针，将头指针指向新链表的头节点。
2. 分别定义两个指针p和q，p指向第一个链表的头结点，q指向第二个链表的头结点。
3. 循环比较p和q指向的节点的值，将值较小的节点接入新链表，并将指针后移。
4. 当p或q其中一个指针为空时，停止循环。
5. 若p非空，则将p后面的节点全部接入新链表。
6. 若q非空，则将q后面的节点全部接入新链表。
7. 返回新链表的头节点。

代码示例：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)  # 创建一个哑结点作为新链表的头节点
    cur = dummy  # 当前结点指针
    
    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    
    if l1:
        cur.next = l1
    if l2:
        cur.next = l2
    
    return dummy.next

以上代码通过比较两个链表的节点值大小，不断将较小的值的节点添加到新链表中，直到其中一个链表为空。然后直接将另一个链表剩余的部分添加到新链表的末尾。最后返回新链表的头节点，即为合并后的递增单链表。