将两个有序线性表合并成一个有序线性表

将两个有序线性表合并成一个有序线性表的方法是，从两个线性表的第一个元素开始比较，将较小的元素插入到新的有序线性表中，然后将指针向后移动，继续比较，直到其中一个线性表的元素全部插入到新的有序线性表中，最后将另一个线性表的剩余元素插入到新的有序线性表中即可。这样就可以得到一个有序的线性表。

相关问题

编写一个算法，将两个有序线性表合并成一个有序线性表。用C语言

在C语言中，可以编写一个归并排序的思想来进行两个有序线性表的合并。这里提供一个基本的递归函数实现：

#include <stdio.h>

// 定义结构体表示链表节点
typedef struct ListNode {
    int val;      // 节点值
    struct ListNode *next; // 指向下一个节点的指针
} ListNode;

// 合并两个已排序的链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 创建新的头结点
    ListNode* head = NULL;
    ListNode* tail = NULL;
    
    // 判断两个链表是否都为空
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;
    
    // 如果第一个链表的第一个节点小于第二个链表的第一个节点，则添加第一个链表的节点到结果
    if (l1->val <= l2->val) {
        if (head == NULL) {
            head = tail = l1;
        } else {
            tail->next = l1;
            tail = l1;
        }
        l1 = l1->next;
    } else {
        if (head == NULL) {
            head = tail = l2;
        } else {
            tail->next = l2;
            tail = l2;
        }
        l2 = l2->next;
    }

    // 递归处理剩余的链表
    while (l1 != NULL && l2 != NULL) {
        if (l1->val <= l2->val) {
            if (tail == NULL) {
                tail = l1;
            } else {
                tail->next = l1;
                tail = l1;
            }
            l1 = l1->next;
        } else {
            if (tail == NULL) {
                tail = l2;
            } else {
                tail->next = l2;
                tail = l2;
            }
            l2 = l2->next;
        }
    }

    // 将未遍历完的链表添加到结果中
    if (l1 != NULL) {
        tail->next = l1;
    } else {
        tail->next = l2;
    }

    return head;
}

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

int main() {
    // 创建两个示例链表
    ListNode* list1 = malloc(sizeof(ListNode));
    list1->val = 1;
    list1->next = malloc(sizeof(ListNode));
    list1->next->val = 3;
    list1->next->next = NULL;

    ListNode* list2 = malloc(sizeof(ListNode));
    list2->val = 2;
    list2->next = malloc(sizeof(ListNode));
    list2->next->val = 4;
    list2->next->next = NULL;

    // 合并链表
    ListNode* mergedList = mergeTwoLists(list1, list2);

    // 打印合并后的链表
    printList(mergedList);

    return 0;
}

这个程序首先比较两个链表的第一个节点，然后逐个比较并添加较小的节点到新链表中，直到其中一个链表遍历完。剩下的部分则直接添加到新链表的末尾。

编写一个算法，将两个有序线性表合并成一个有序线性表。用数据结构

当需要将两个已排序的线性表合并成一个新的、按升序排列的线性表时，可以采用双指针法。这是一种简单而直观的方法，步骤如下：

1. 初始化两个指针，分别指向第一个线性表的头部（headA）和第二个线性表的头部（headB），以及一个新的空线性表（result）。

2. 创建一个临时存储节点的变量（temp），用于临时存放正在合并的较小元素。

3. 当两个指针都未到达各自线性表的末尾时，比较当前两个指针所指向的节点值：

- 如果头A的值小于头B的值，将头A的节点添加到结果列表，并将头A向后移动一位；
- 否则，将头B的节点添加到结果列表，并将头B向后移动一位。

4. 继续这个过程，直到其中一个线性表的指针达到其结尾。然后将另一个线性表剩余部分的节点依次添加到结果列表。

5. 最后，将结果列表的所有节点连接起来，就得到了合并后的有序线性表。

Python伪代码示例：

def merge_sorted_lists(listA, listB):
    result = []
    pointerA = pointerB = 0

    while pointerA < len(listA) and pointerB < len(listB):
        if listA[pointerA] <= listB[pointerB]:
            result.append(listA[pointerA])
            pointerA += 1
        else:
            result.append(listB[pointerB])
            pointerB += 1

    # 添加剩余部分，如果有的话
    result.extend(listA[pointerA:])
    result.extend(listB[pointerB:])

    return result

# 示例：
listA = [1, 3, 5]
listB = [2, 4, 6]
merged_list = merge_sorted_lists(listA, listB)