两个有序链表的合并

好的，这个问题可以使用归并排序的思想来解决。具体步骤如下：

1. 定义一个新的链表，作为合并后的链表。
2. 分别遍历两个有序链表，比较当前节点的值大小，将较小的节点插入新链表中，并将该链表的指针后移。
3. 循环执行步骤2，直到其中一个链表为空。
4. 将另一个链表中余下的节点直接插入新链表中。
5. 返回新链表。

下面是一个示例代码：

def merge_two_lists(l1, l2):
    dummy = ListNode(-1)
    curr = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    
    if l1:
        curr.next = l1
    else:
        curr.next = l2
    
    return dummy.next

其中，`ListNode` 是一个链表节点的定义，`l1` 和 `l2` 分别表示两个有序链表的头节点。

相关问题

c语言写两个有序链表合并

当我们需要合并两个有序链表时，我们可以使用迭代的方式来解决这个问题。首先，我们需要定义一个新的链表头节点，并设置一个指针用于遍历两个链表。然后，我们比较两个指针所指向的节点的值，将较小的节点添加到新链表中，并将指针向后移动。重复这个过程，直到其中一个链表遍历完毕。最后，将剩余链表的节点直接添加到新链表的末尾。

下面是使用C语言实现这个算法的示例代码：

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

// 定义链表节点结构体
struct ListNode {
    int val;
    struct ListNode* next;
};

// 创建新节点
struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 合并两个有序链表
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    // 创建一个新的链表头节点
    struct ListNode* dummy = createNode(0);
    // 用于遍历新链表和两个原始链表
    struct ListNode* cur = dummy;

    while (l1 != NULL && l2 != NULL) {
        // 比较两个节点的值
        if (l1->val <= l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }

    // 将剩余链表的节点直接添加到新链表的末尾
    if (l1 != NULL) {
        cur->next = l1;
    }
    if (l2 != NULL) {
        cur->next = l2;
    }

    return dummy->next;
}

// 打印链表
void printList(struct ListNode* head) {
    struct ListNode* cur = head;
    while (cur != NULL) {
        printf("%d ", cur->val);
        cur = cur->next;
    }
    printf("\n");
}

int main() {
    // 创建两个有序链表
    struct ListNode* l1 = createNode(1);
    l1->next = createNode(3);
    l1->next->next = createNode(5);

    struct ListNode* l2 = createNode(2);
    l2->next = createNode(4);
    l2->next->next = createNode(6);

    // 合并两个有序链表
    struct ListNode* mergedList = mergeTwoLists(l1, l2);

    // 打印合并后的链表
    printf("Merged List: ");
    printList(mergedList);

    return 0;
}

运行上述代码，输出结果为：

Merged List: 1 2 3 4 5 6

这是将两个有序链表合并成一个有序链表的基本思路和实现方法。希望对你有帮助！

JAVA 将两个有序链表合并为一个有序链表

JAVA可以通过以下步骤将两个有序链表合并为一个有序链表：

1. 创建一个新的链表头节点`newNode`和指针`tmp`，用来构建合并后的有序链表。
2. 设置两个链表的头结点分别为`head1`和`head2`。
3. 比较`head1`和`head2`节点的值，将较小的节点连接到`tmp`节点的后面，然后将指针`tmp`指向新加入的节点。
4. 移动被选中的节点所在的链表的头指针，即将`head1`或`head2`指向下一个节点。
5. 重复步骤3和步骤4，直到其中一个链表走完。
6. 当其中一个链表走完后，将另一个链表剩下的节点直接连接到`tmp`节点的后面，使其`tmp.next = head1/head2`。
7. 返回新的链表头节点`newNode.next`即为合并后的有序链表。

通过以上步骤，JAVA可以将两个有序链表合并为一个有序链表。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [合并两个有序链表（java）](https://blog.csdn.net/intmainreturn/article/details/128490890)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [合并两个有序链表（Java）](https://blog.csdn.net/m0_63036262/article/details/124417509)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]