递增有序单链表L1、L2，不申请新结点，利用原表结点对两表进行合并，并使得合并后成为一个集合，合并后用L1的头结点作为头结点，删除多余的结点，删除L2的头结点。

算法步骤如下：

1. 定义指针p1、p2分别指向L1的头结点和L2的头结点。

2. 若L1为空，则直接让L1指向L2，返回L1。

3. 若L2为空，则直接返回L1。

4. 若L1和L2均不为空，则从头开始比较L1和L2的结点大小，将小的结点接到新的链表中。

5. 每次比较时将p1或p2指向下一个结点，直到p1或p2为空。

6. 若p1为空，则将p2接到新的链表中。

7. 若p2为空，则新的链表已经包含了L1和L2的所有结点，不需要再做处理。

8. 最后删除L2的头结点，返回L1。

相关问题

编写将两个带头结点的递增有序单链表l1和l2合并为一个非递减的有序单链表l1的算法 merge( linklist &l1, linklist &l2 )，要求直接使用原链表中的结点。

算法思路：

1. 定义两个指针p1和p2分别指向链表l1和l2的第一个结点（即头结点的下一个结点）；

2. 定义一个指针p3指向新链表l3的头结点；

3. 比较p1和p2所指向的结点的值，将较小的结点插入到新链表l3的尾部，并将指向该结点的指针后移；

4. 重复步骤3，直到p1或p2为空；

5. 将p1或p2剩余的结点插入到新链表l3的尾部；

6. 返回新链表l3的头结点。

算法实现：

typedef struct node {
    int data;
    struct node *next;
} Node, *LinkList;

LinkList merge(LinkList &l1, LinkList &l2) {
    LinkList p1 = l1->next, p2 = l2->next, p3 = l1;
    while (p1 && p2) {
        if (p1->data <= p2->data) {
            p3->next = p1;
            p1 = p1->next;
        } else {
            p3->next = p2;
            p2 = p2->next;
        }
        p3 = p3->next;
    }
    p3->next = p1 ? p1 : p2;
    return l1;
}

注：本算法假设链表中不含有重复元素。如果链表中含有重复元素，需要对算法进行修改。

编写将两个带头结点的递增有序单链表L1和L2合并为一个非递减的有序单链表L1的算法 Merge(Li nkList &L1, LinkList &L2)，

要编写一个合并两个递增有序链表 `L1` 和 `L2` 的算法，可以采用迭代或者递归的方式。这里我们提供一种迭代的解决方案：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* mergeTwoLists(ListNode* L1, ListNode* L2) {
    // 创建一个新的头节点作为结果链表
    ListNode* head = new ListNode(0);
    ListNode* tail = head;

    while (L1 != NULL && L2 != NULL) {
        // 如果 L1 的值小于 L2 的值，将 L1 的元素添加到结果链表
        if (L1->val <= L2->val) {
            tail->next = L1;
            L1 = L1->next;
        } else {
            // 否则，将 L2 的元素添加到结果链表
            tail->next = L2;
            L2 = L2->next;
        }
        // 移动 tail 指针以便继续比较下一个节点
        tail = tail->next;
    }

    // 如果其中一个链表还有剩余元素，直接将其添加到结果链表尾部
    if (L1 != NULL) {
        tail->next = L1;
    } else {
        tail->next = L2;
    }

    return head->next;  // 返回合并后的链表头节点
}

在这个算法中，我们不断比较 `L1` 和 `L2` 的当前节点值，将较小的节点添加到新链表中，并更新指针。当有一个链表遍历完后，我们将另一个链表剩下的部分添加到结果链表的尾部。