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

首先，我们可以创建一个新的链表s3来存储合并后的序列。同时，我们需要定义两个指针p1和p2，分别指向s1和s2的头结点。

接下来，我们比较p1指向的节点与p2指向的节点的大小关系，将较小的节点加入s3中，并将指向该节点的指针后移一位。然后再次比较指针指向的节点的大小，重复以上步骤，直到任一链表的指针指向了末尾节点。

如果s1链表的节点已经全部添加到s3中，但s2链表仍有节点未添加，则将s2链表中剩余的节点依次添加到s3中。反之亦然。

最后返回s3即可。

代码如下：

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

def mergeList(s1: ListNode, s2: ListNode) -> ListNode:
    p1, p2 = s1, s2
    dummy = ListNode(None)
    p3 = dummy
    while p1 and p2:
        if p1.val < p2.val:
            p3.next = p1
            p1 = p1.next
        else:
            p3.next = p2
            p2 = p2.next
        p3 = p3.next
    p3.next = p1 if p1 else p2
    return dummy.next

相关问题

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

好的，让我看看可以为您服务！关于您的第一个问题，可以使用双指针来解决。首先，我们需要新建一个链表用于存储交集。然后，我们使用两个指针分别指向两个链表的头节点，并比较它们的值。如果两个值相同，则将该值添加到新链表中。如果S1当前节点的值小于S2当前节点的值，则S1向后移动一个节点，反之，则S2向后移动一个节点。直到一个链表遍历完成，则停止遍历。最终，新建的链表S3即为S1与S2的交集。

以下是C++代码实现：

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

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    ListNode* res = new ListNode(0);
    ListNode* cur = res;
    while (headA != NULL && headB != NULL) {
        if (headA->val == headB->val) {
            cur->next = new ListNode(headA->val);
            cur = cur->next;
            headA = headA->next;
            headB = headB->next;
        } else if (headA->val < headB->val) {
            headA = headA->next;
        } else {
            headB = headB->next;
        }
    }
    return res->next;
}

注意：这个函数不会判断S1与S2是否为非降序链表序列，需要在调用该函数前自己先进行判断。

已知两个非降序链表序列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;
}