02-线性结构1 两个有序链表序列的合并

### 回答1：
假设有两个已经按照升序排列的链表，要将它们合并成一个新的有序链表。可以按照以下步骤实现：

1. 定义一个新链表，并用一个指针指向它的头部。
2. 比较两个链表的头部节点，将较小的节点加入新链表，并将指针指向这个节点。
3. 重复步骤2，直到其中一个链表为空。
4. 将另一个非空的链表加入新链表的末尾。

实现代码可以类似下面这样：

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)
    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

其中，dummy节点是用于返回新链表的头部的。curr指针用于在遍历链表的过程中连接新节点。最后返回dummy节点的下一个节点就是新链表的头部。

### 回答2：
对于两个有序链表序列的合并问题，可以采用递归算法实现。具体过程如下：

1. 若其中一个链表为空，则直接返回另一个链表作为结果。
2. 比较两个链表的头节点的数据大小，取较小的节点作为新的头节点。
3. 将剩余的链表继续调用递归函数，将返回的结果接在新的头节点后面。
4. 返回新的合并后的链表。

示例代码如下：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def merge_lists(head1, head2):
    if not head1:
        return head2
    if not head2:
        return head1
    if head1.data < head2.data:
        new_head = head1
        new_head.next = merge_lists(head1.next, head2)
    else:
        new_head = head2
        new_head.next = merge_lists(head1, head2.next)
    return new_head

时间复杂度为 $O(m+n)$，其中 $m$ 和 $n$ 分别为两个链表的长度。由于采用了递归算法，会使用额外的栈空间，空间复杂度为 $O(m+n)$。需要注意的是，在实际代码中需要注意边界条件的判断和对链表的操作，避免出现空指针引用等错误。

### 回答3：
线性结构是数据结构中最基本的结构之一，常见的线性结构有数组、链表、栈、队列等。有序链表是将元素按照一定规则有序排列的链表。合并两个有序链表，是指将两个有序链表中的元素按照一定规则合并成一个新的有序链表。这个问题可以分为如下的几个步骤进行解决：

1.创建一个新的头结点来作为新链表的头结点。

2.扫描两个链表中的元素，找到其中较小的元素，并将其插入到新链表的尾部。

3.重复步骤2，直到其中一个链表为空。

4.将另一个链表中剩余的元素插入到新链表的尾部即可。

下面是具体的代码实现:

/*定义链表结构体*/
typedef struct Node{
    int data; /*数据域*/
    struct Node* next; /*指针域*/
}LinkList;

/*合并两个有序链表*/
LinkList* merge(LinkList* l1, LinkList* l2){
    LinkList* head = (LinkList *)malloc(sizeof(LinkList)); /*新链表的头结点*/
    LinkList* p = head; /*新链表的尾指针*/
    LinkList* p1 = l1->next; /*l1的第一个结点*/
    LinkList* p2 = l2->next; /*l2的第一个结点*/

    while(p1 != NULL && p2 != NULL)
    {
        if(p1->data < p2->data) /*l1中的元素小*/
        {
            p->next = p1; /*将l1中的结点插入到新链表的尾部*/
            p1 = p1->next; /*指针后移*/
        }
        else /*l2中的元素小*/
        {
            p->next = p2; /*将l2中的结点插入到新链表的尾部*/
            p2 = p2->next; /*指针后移*/
        }

        p = p->next; /*新链表的尾指针后移*/
    }

    /*将剩余元素插入到新链表的尾部*/
    if(p1 != NULL) 
    {
        p->next = p1;
    }
    else 
    {
        p->next = p2;
    }

    return head; /*返回新链表的头结点*/
}

总体来说，合并两个有序链表需要依次比较两个链表中的元素，并将小的元素插入到新的有序链表中。这个过程需要用到新建链表的头结点来保存新链表的头指针，以及尾指针来记录新链表的结尾。最后，如果其中一个链表还有剩余元素，也要将其插入到新链表中。