c语言将两个单链表合并为一个单链表

在C语言中，合并两个已排序的单链表可以采用递归或迭代的方式实现。这里简单介绍一种常见的迭代方法：

1. 创建一个新的头节点 `newHead` 和两个指针 `p1` 指向第一个链表的头节点，`p2` 指向第二个链表的头节点。

2. 初始化三个指针 `current`, `prev` 和 `next`，分别指向当前节点、前一个节点和下一个节点。初始时，`current` 设置为 `newHead`，`prev` 设为 `NULL`。

3. 使用一个 `while` 循环，判断 `p1` 和 `p2` 是否都不为空：
- 如果 `p1` 或者 `p2` 任一为空，将另一个非空链表的剩余部分接到 `newHead` 的后面。
- 否则，比较 `p1` 和 `p2` 的值，选择较小的一个作为新的当前节点 `current`，然后移动对应的指针（前进到下一个节点），同时将这个节点设置为 `prev` 的下一个节点。
- 再次检查 `p1` 和 `p2`，直到它们都为空。

4. 当循环结束时，将 `prev` 指向的新节点设为合并后的链表的最后一个节点，因为 `prev` 最后会指向合并后的最后一个元素。

以下是合并过程的伪代码示例：

struct Node *mergeSortedLists(struct Node* head1, struct Node* head2) {
    struct Node* newHead = NULL;
    struct Node* current = newHead;
    struct Node* prev = NULL;

    while (head1 != NULL && head2 != NULL) {
        if (head1->data <= head2->data) {
            if (current == newHead) {
                current = head1;
            } else {
                prev->next = head1;
            }
            head1 = head1->next;
        } else {
            if (current == newHead) {
                current = head2;
            } else {
                prev->next = head2;
            }
            head2 = head2->next;
        }
        prev = current;
    }

    // 将剩余链表连接到新链表的末尾
    if (head1 != NULL) {
        prev->next = head1;
    } else {
        prev->next = head2;
    }

    return newHead;
}