已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的并集新非降序链表S3。

好的，这是一个经典的链表问题。我们可以使用双指针来遍历两个链表，比较节点大小，将较小的节点加入新链表中。具体实现可以参考以下代码：

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

相关问题

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的并集新非降序链表S3。C++语言

可以使用双指针法来实现。具体步骤如下：

1. 定义三个指针，分别指向S1、S2、S3的头结点。
2. 比较S1和S2当前节点的大小，将较小的节点插入到S3中，并将指向该节点的指针后移一位。
3. 重复步骤2，直到S1或S2中的一个链表遍历完毕。
4. 将未遍历完的链表中的剩余节点插入到S3中。

以下是C++代码实现：

ListNode* merge(ListNode* S1, ListNode* S2) {
    ListNode* S3 = new ListNode(0);
    ListNode* p1 = S1;
    ListNode* p2 = S2;
    ListNode* p3 = S3;

    while (p1 != nullptr && p2 != nullptr) {
        if (p1->val <= p2->val) {
            p3->next = p1;
            p1 = p1->next;
        } else {
            p3->next = p2;
            p2 = p2->next;
        }
        p3 = p3->next;
    }

    if (p1 != nullptr) {
        p3->next = p1;
    }

    if (p2 != nullptr) {
        p3->next = p2;
    }

    return S3->next;
}

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的并集新非降序链表S3。C++语言完整

好的，以下是代码实现：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* merge(ListNode* S1, ListNode* S2) {
    if (!S1) return S2;
    if (!S2) return S1;
    ListNode* head = new ListNode(0);
    ListNode* cur = head;
    while (S1 && S2) {
        if (S1->val <= S2->val) {
            cur->next = S1;
            S1 = S1->next;
        } else {
            cur->next = S2;
            S2 = S2->next;
        }
        cur = cur->next;
    }
    cur->next = S1 ? S1 : S2;
    return head->next;
}

int main() {
    ListNode* S1 = new ListNode(1);
    S1->next = new ListNode(3);
    S1->next->next = new ListNode(5);
    ListNode* S2 = new ListNode(2);
    S2->next = new ListNode(4);
    S2->next->next = new ListNode(6);
    ListNode* S3 = merge(S1, S2);
    while (S3) {
        cout << S3->val << " ";
        S3 = S3->next;
    }
    return 0;
}