将两个递增的有序链表合并为一个递增的有序链表代码

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(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
    # 将剩余的节点接到新链表的末尾
    cur.next = l1 if l1 else l2
    # 返回哨兵节点的下一个节点
    return dummy.next

相关问题

两个递增有序链表合并成一个递增有序链表cpp

在C++中，合并两个递增有序链表可以使用迭代或递归的方式来实现。这里我将提供一种迭代的方法，因为它更直观且效率更高。假设我们有两个头结点为`head1`和`head2`的递增排序链表。

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* mergeTwoLists(ListNode* head1, ListNode* head2) {
    // 创建一个新的空链表作为结果
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy; // 当前指针

    // 当其中一个链表为空时，直接返回另一个链表
    while (head1 && head2) {
        if (head1->val < head2->val) { // 如果第一个值小，添加第一个并移动指针
            current->next = head1;
            head1 = head1->next;
        } else { // 否则，添加第二个值
            current->next = head2;
            head2 = head2->next;
        }
        current = current->next; // 移动到下一个位置
    }

    // 将剩余未处理的部分添加到结果链表中
    if (head1) {
        current->next = head1;
    } else {
        current->next = head2;
    }

    return dummy->next; // 返回新合并后的链表头节点
}

在这个函数中，我们首先创建一个虚拟头节点`dummy`用于简化边界情况的处理。然后通过比较两个链表当前节点的值，不断选择较小的那个节点添加到结果链表中，并更新指针。最后返回合并后的链表头节点。

c语言数据结构代码实现将两个非递增有序链表合并为一个新的非递增有序链表并返回

下面是C语言的代码实现：

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

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

struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
struct ListNode dummy;
struct ListNode* tail = &dummy;

while (l1 && l2) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;

return dummy.next;
}

int main() {
struct ListNode *node1, *node2, *node3, *node4, *result;

// 构造链表1
node1 = (struct ListNode*)malloc(sizeof(struct ListNode));
node2 = (struct ListNode*)malloc(sizeof(struct ListNode));
node3 = (struct ListNode*)malloc(sizeof(struct ListNode));
node1->val = 5; node2->val = 3; node3->val = 1;
node1->next = node2; node2->next = node3; node3->next = NULL;

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

// 合并两个链表
result = merge(node1, node2);

// 打印结果
while (result) {
printf("%d ", result->val);
result = result->next;
}

return 0;
}

输出结果：6 5 4 3 2 1