C语言算法-解答合并两个有序链表问题的C语言实现

题目

给定两个按非递减顺序排列的链表 l1 和 l2，合并两个链表，并将其作为一个新链表返回。新链表应该通过拼接前两个链表的节点来完成。

引言

合并两个有序链表问题需要考虑链表的指针操作和比较大小的逻辑。我们可以使用迭代的方法或递归的方法来解决这个问题。解决这个问题需要对链表进行遍历和指针操作。

算法思路

我们将使用迭代的方法来解决合并两个有序链表问题。

算法的步骤如下：

1. 创建一个新链表的虚拟头结点 dummy，并用一个指针 current 指向 dummy。

2. 遍历链表 l1 和 l2，直到其中一个链表为空：

   • 如果 l1 的当前节点的值小于等于 l2 的当前节点的值，将 current 的下一个节点指向 l1 的当前节点，并将 l1 的指针向后移动一位。
   • 如果 l1 的当前节点的值大于 l2 的当前节点的值，将 current 的下一个节点指向 l2 的当前节点，并将 l2 的指针向后移动一位。
   • 将 current 的指针向后移动一位。
3. 将非空的链表剩余部分直接连接到 current 的下一个节点。
4. 返回新链表的头结点，即虚拟头结点 dummy 的下一个节点。

代码实现

下面是使用C语言实现的代码：

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

typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
    ListNode* current = dummy;

    while (l1 != NULL && l2 != NULL) {
        if (l1->val <= l2->val) {
            current->next = l1;
            l1 = l1->next;
        } else {
            current->next = l2;
            l2 = l2->next;
        }
        current = current->next;
    }

    if (l1 != NULL) {
        current->next = l1;
    }

    if (l2 != NULL) {
        current->next = l2;
    }

    ListNode* result = dummy->next;
    free(dummy);

    return result;
}

void printList(ListNode* head) {
    ListNode* current = head;

    while (current != NULL) {
        printf("%d ", current->val);
        current = current->next;
    }

    printf("\n");
}

int main() {
    // 创建示例链表1: 1 -> 2 -> 4
    ListNode* l1 = (ListNode*)malloc(sizeof(ListNode));
    l1->val = 1;

    ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
    node1->val = 2;
    l1->next = node1;

    ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
    node2->val = 4;
    node1->next = node2;
    node2->next = NULL;

    // 创建示例链表2: 1 -> 3 -> 4
    ListNode* l2 = (ListNode*)malloc(sizeof(ListNode));
    l2->val = 1;

    ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
    node3->val = 3;
    l2->next = node3;

    ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));
    node4->val = 4;
    node3->next = node4;
    node4->next = NULL;

    printf("List 1: ");
    printList(l1);

    printf("List 2: ");
    printList(l2);

    ListNode* result = mergeTwoLists(l1, l2);

    printf("Merged List: ");
    printList(result);

    // 释放内存
    while (result != NULL) {
        ListNode* temp = result;
        result = result->next;
        free(temp);
    }

    return 0;
}

算法分析

该算法只需要对两个链表进行一次遍历，并在新链表上进行指针操作，所以时间复杂度为 O(n + m)，其中 n 和 m 分别是两个链表的长度。

空间复杂度为 O(1)，算法只使用了常数级别的额外空间。

示例和测试

示例输入1:

List 1: 1 -> 2 -> 4
List 2: 1 -> 3 -> 4

示例输出1:

Merged List: 1 -> 1 -> 2 -> 3 -> 4 -> 4

示例输入2:

List 1: 
List 2: 

示例输出2:

Merged List: 空链表

示例输入3:

List 1: 1 -> 2 -> 3
List 2: 

示例输出3:

Merged List: 1 -> 2 -> 3

总结

本文使用C语言实现了解答合并两个有序链表问题的代码。通过使用迭代的方法，我们能够将两个有序链表合并为一个新的有序链表。该算法的时间复杂度为 O(n + m)，空间复杂度为 O(1)。