算法设计题：将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。用C语言写

在C语言中，我们可以使用迭代的方式来解决这个问题。首先创建一个新的头节点，然后遍历两个输入链表，比较当前节点的值。选择较小的一个添加到新链表中，并将其指针更新到下一个节点，直到其中一个链表遍历完。如果另一个链表还有剩余元素，则把剩余部分添加到最后。

以下是算法的基本步骤：

1. 创建一个新的单链表结构体 `ListNode` 和一个空头结点 `newHead`。
2. 定义三个指针 `p1`, `p2` 分别指向两个输入链表的头部，以及 `current` 指向 `newHead`。
3. 使用循环（while p1 或 p2 不为空）：
a. 如果 p1 的值小于等于 p2 的值，将 p1 的数据插入到 `current->next`，并将 `current` 更新为 `p1`。
- 将 p1 向前移动一位。
b. 否则，将 p2 的数据插入到 `current->next`，并将 `current` 更新为 `p2`。
- 同样，将 p2 向前移动一位。
4. 当遍历结束后，如果 `p1` 还未到达末尾，说明第一个链表的剩余部分大于第二个链表，那么将 `p1` 的剩余部分接到 `newHead` 后面。
5. 返回新的头结点 `newHead`。

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

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* newHead = NULL, *current = newHead;
    
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            current->next = l1;
            l1 = l1->next;
        } else {
            current->next = l2;
            l2 = l2->next;
        }
        current = current->next;
    }

    // 如果有一个链表还没结束，直接接上
    if (l1)
        current->next = l1;
    else if (l2)
        current->next = l2;

    return newHead;
}