7-9 两个有序链表序列的合并 c语言

可以使用归并排序的思想，将两个有序链表合并成一个有序链表。具体实现可以参考以下代码：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}

相关问题

7-51 两个有序链表序列的合并使用C语言实现

以下是使用C语言实现合并两个有序链表序列的代码：

#include <stdio.h>
#include <stdlib.h>

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

// 合并两个有序链表
Node *mergeLists(Node *list1, Node *list2) {
    Node *head = NULL; // 合并后链表的头节点
    Node *tail = NULL; // 合并后链表的尾节点

    // 如果有一个链表为空，则直接返回另一个链表
    if (list1 == NULL) {
        return list2;
    } else if (list2 == NULL) {
        return list1;
    }

    // 选择头节点
    if (list1->value < list2->value) {
        head = list1;
        list1 = list1->next;
    } else {
        head = list2;
        list2 = list2->next;
    }
    tail = head;

    // 循环合并两个链表
    while (list1 != NULL && list2 != NULL) {
        if (list1->value < list2->value) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }

    // 将剩余的节点添加到尾部
    if (list1 != NULL) {
        tail->next = list1;
    } else {
        tail->next = list2;
    }

    return head;
}

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

int main() {
    // 创建两个有序链表
    Node *list1 = (Node *) malloc(sizeof(Node));
    list1->value = 1;
    list1->next = (Node *) malloc(sizeof(Node));
    list1->next->value = 3;
    list1->next->next = (Node *) malloc(sizeof(Node));
    list1->next->next->value = 5;
    list1->next->next->next = NULL;

    Node *list2 = (Node *) malloc(sizeof(Node));
    list2->value = 2;
    list2->next = (Node *) malloc(sizeof(Node));
    list2->next->value = 4;
    list2->next->next = (Node *) malloc(sizeof(Node));
    list2->next->next->value = 6;
    list2->next->next->next = NULL;

    // 合并两个有序链表
    Node *mergedList = mergeLists(list1, list2);

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

    return 0;
}

输出结果为：

1 2 3 4 5 6

两个有序链表序列的合并C语言

可以使用指针操作来实现两个有序链表的合并，具体的实现过程如下：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    // 创建一个哨兵节点
    struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = NULL;

    // 定义两个指针分别指向两个链表的头节点
    struct ListNode *p1 = l1, *p2 = l2;
    // 定义一个指针指向哨兵节点
    struct ListNode *p = dummy;

    // 如果两个链表都不为空，则比较两个链表的头节点的大小
    while (p1 != NULL && p2 != NULL) {
        if (p1->val < p2->val) {
            p->next = p1;
            p1 = p1->next;
        } else {
            p->next = p2;
            p2 = p2->next;
        }
        p = p->next;
    }

    // 如果链表1不为空，则将链表1剩余部分添加到合并后的链表中
    if (p1 != NULL) {
        p->next = p1;
    }
    // 如果链表2不为空，则将链表2剩余部分添加到合并后的链表中
    if (p2 != NULL) {
        p->next = p2;
    }

    // 返回合并后的链表
    return dummy->next;
}

// 主函数
int main() {
    // 创建两个有序链表
    struct ListNode *l1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    l1->val = 1;
    struct ListNode *node1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    node1->val = 2;
    l1->next = node1;
    node1->next = NULL;

    struct ListNode *l2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    l2->val = 1;
    struct ListNode *node2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    node2->val = 3;
    l2->next = node2;
    node2->next = NULL;

    // 合并两个有序链表
    struct ListNode *mergedList = mergeTwoLists(l1, l2);

    // 输出合并后的链表
    while (mergedList != NULL) {
        printf("%d ", mergedList->val);
        mergedList = mergedList->next;
    }
    printf("\n");

    return 0;
}

上述代码中，首先定义了一个哨兵节点(dummy)作为合并后的链表的头节点，然后定义了两个指针p1和p2分别指向两个链表的头节点，定义另外一个指针p指向哨兵节点。接着按照从小到大的顺序将两个链表的节点依次添加到合并后的链表中，最后返回合并后的链表即可。