题目描述 已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。 输入格式 输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

好的，我的回答如下：

可以使用双指针法，分别指向两个链表的头节点，比较两个节点的大小，将较小的节点加入到新的链表中，并将指针后移。直到其中一个链表为空，将另一个链表剩余的节点加入到新的链表中即可。

代码如下：

def merge(s1, s2):
    p1, p2 = s1, s2
    dummy = ListNode(-1)
    cur = dummy
    while p1 and p2:
        if p1.val <= p2.val:
            cur.next = p1
            p1 = p1.next
        else:
            cur.next = p2
            p2 = p2.next
        cur = cur.next
    if p1:
        cur.next = p1
    if p2:
        cur.next = p2
    return dummy.next

相关问题

已知两个非降序链表序列s1与s2，设计函数构造出s1与s2合并后的新的非降序链表s3

### 回答1：
可以使用归并排序的思想来实现。

定义两个指针分别指向s1和s2的头部，比较它们所指向的节点的值，将值小的节点加入s3中，并将相应指针向后移动。重复上述过程直到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()
    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 or l2
    return dummy.next

这里我们使用了虚拟头节点dummy来简化操作。

### 回答2：
假设两个非降序链表序列s1和s2如下所示：

s1: 1 -> 3 -> 5 -> 7 -> 9
s2: 2 -> 4 -> 6 -> 8 -> 10

要将它们合并成一个新的非降序链表s3，我们可以采用如下思路：

1. 新建一个空链表s3，并定义两个指针p和q，分别指向s1和s2的第一个节点。

2. 比较p和q所指向的节点的大小，将较小的节点添加到s3链表的末尾，并移动相应的指针。

3. 重复步骤2，直到其中一个指针到达了链表的末尾。此时，将另一个链表的剩余节点添加到s3链表的末尾即可。

具体的实现代码如下所示：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* head = NULL;
struct ListNode* tail = NULL;
struct ListNode* p = l1;
struct ListNode* q = l2;

while (p != NULL && q != NULL) {
if (p->val < q->val) {
if (head == NULL) {
head = p;
tail = p;
} else {
tail->next = p;
tail = p;
}
p = p->next;
} else {
if (head == NULL) {
head = q;
tail = q;
} else {
tail->next = q;
tail = q;
}
q = q->next;
}
}

if (p != NULL) {
if (head == NULL) {
head = p;
} else {
tail->next = p;
}
}

if (q != NULL) {
if (head == NULL) {
head = q;
} else {
tail->next = q;
}
}

return head;
}

对于上面的代码，首先定义了head和tail两个指针用于指向s3链表的头和尾，同时定义了p和q指针分别指向s1和s2链表的第一个节点。然后，在while循环中，如果p所指节点小于q所指节点，就将p所指节点添加到s3链表末尾，并移动p指针；否则，将q所指节点添加到s3链表末尾，并移动q指针。最后，如果s1或s2链表中还有剩余节点，就将其添加到s3链表末尾即可。最后，返回s3链表的头指针head即可。

通过上面的实现，我们可以将两个非降序链表序列合并成一个新的非降序链表。

### 回答3：
假设两个非降序链表序列s1和s2分别为：

s1: 1->3->5->7->9
s2: 2->4->6->8->10

我们要将s1和s2合并成一个新的非降序链表s3，我们可以从s1和s2的头结点开始逐个比较大小，将较小的结点加入到s3中，并将指针向后移动。

具体步骤如下：

1. 定义三个指针分别指向s1、s2和s3的头结点，假设分别为p1、p2、p3，初始时p3为NULL。

2. 比较p1和p2指向的结点的大小，选择较小的结点加入到s3中，并将指针向后移动，直到p1或p2指向NULL，此时退出循环。

3. 如果p1不为NULL，将p1指向的剩余结点接到s3的末尾。

4. 如果p2不为NULL，将p2指向的剩余结点接到s3的末尾。

5. 返回s3的头结点。

具体实现代码如下：

ListNode* merge(ListNode* s1, ListNode* s2) {
ListNode* p1 = s1;
ListNode* p2 = s2;
ListNode* p3 = NULL;
ListNode* s3 = NULL;

while (p1 != NULL && p2 != NULL) {
ListNode* tmp = new ListNode();
if (p1->val <= p2->val) {
tmp->val = p1->val;
p1 = p1->next;
} else {
tmp->val = p2->val;
p2 = p2->next;
}

if (s3 == NULL) {
s3 = tmp;
p3 = s3;
} else {
p3->next = tmp;
p3 = p3->next;
}
}

if (p1 != NULL) {
if (s3 == NULL) {
s3 = p1;
} else {
p3->next = p1;
}
}

if (p2 != NULL) {
if (s3 == NULL) {
s3 = p2;
} else {
p3->next = p2;
}
}

return s3;
}

上述实现代码中，我们使用了新建一个空结点tmp来承载较小的结点，并将tmp加入到s3中。我们还使用了p3指针指向s3的末尾，方便将新结点接到s3的末尾。

需要注意的是，我们要记得释放空结点的内存，否则可能造成内存泄漏。

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

算法思路：

可以使用归并排序的思想，将S1和S2中的元素逐个比较，将较小的元素加入S3中，直到S1或S2中的元素遍历完毕。最后，将S1或S2中剩余的元素加入S3中即可。

算法步骤：

1.设置两个指针p1和p2分别指向S1和S2的头结点；

2.比较p1和p2指向的结点的值的大小，将较小的结点加入S3中，并将p1或p2指向下一个结点；

3.如果S1或S2中还有剩余的结点，将其加入S3中。

代码实现：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* p1 = l1; //指向链表l1的指针
    struct ListNode* p2 = l2; //指向链表l2的指针
    struct ListNode* p = NULL; //指向新链表的指针
    struct ListNode* head = NULL; //新链表的头结点
    //判断l1和l2是否为空链表
    if(l1 == NULL) {
        return l2;
    }
    if(l2 == NULL) {
        return l1;
    }
    //确定新链表的头结点
    if(p1->val <= p2->val) {
        head = p1;
        p1 = p1->next;
    } else {
        head = p2;
        p2 = p2->next;
    }
    p = head;
    //将l1和l2中的较小值加入新链表中
    while(p1 && p2) {
        if(p1->val <= p2->val) {
            p->next = p1;
            p1 = p1->next;
        } else {
            p->next = p2;
            p2 = p2->next;
        }
        p = p->next;
    }
    //将l1或l2中剩余的结点加入新链表中
    if(p1) {
        p->next = p1;
    }
    if(p2) {
        p->next = p2;
    }
    return head;
}