编写将两个带头结点的递增有序单链表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，我们要将它们合并为一个递减有序单链表L3。

首先创建一个空链表L3，然后比较L1和L2的头结点，将较小的结点插入到L3的头部。然后，将指向较小结点的指针向后移动一步。再次比较L1和L2的头结点，将较小的结点插入到L3的头部，指向较小结点的指针再向后移动一步。重复这个过程直到其中一个链表为空。

此时，将另一个非空链表的剩余结点插入到L3的头部即可。因为剩余的结点已经是有序的，所以只需要将它们插入到L3的头部即可。

以下是Python代码实现：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_lists(l1: ListNode, l2: ListNode) -> ListNode:
    # 创建一个空链表L3
    dummy = ListNode()
    cur = dummy
    
    # 比较L1和L2的头结点，将较小的结点插入到L3的头部
    while l1 and l2:
        if l1.val < l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    
    # 将剩余结点插入到L3的头部
    if l1:
        cur.next = l1
    if l2:
        cur.next = l2
    
    # 反转L3
    prev = None
    cur = dummy.next
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    
    return prev

、Ha和Hb分别是两个带头结点的递增有序单链表。设计一个算法，将这两个有序链表的所有数据结点合并成一个递增有序的单链表Hc.

要将两个递增有序的单链表合并成一个递增有序的单链表，可以使用双指针法来实现。具体步骤如下：

1. 创建一个新的头结点Hc，并用两个指针p和q分别指向链表Ha和Hb的第一个结点。
2. 比较p和q指向的结点的值，将较小的值作为Hc的下一个结点，并将对应链表的指针后移一位。
3. 重复步骤2，直到其中一个链表遍历完毕。
4. 将未遍历完的链表剩余部分直接连接到Hc的末尾。

下面是具体的算法实现：

def merge_sorted_lists(Ha, Hb):
    # 创建新的头结点Hc
    Hc = ListNode(None)
    # 创建指针p和q分别指向Ha和Hb的第一个结点
    p, q = Ha.next, Hb.next
    # 创建指针r指向Hc的最后一个结点
    r = Hc

    # 比较p和q指向的结点的值，将较小的值作为Hc的下一个结点
    while p and q:
        if p.val <= q.val:
            r.next = p
            p = p.next
        else:
            r.next = q
            q = q.next
        r = r.next

    # 将未遍历完的链表剩余部分直接连接到Hc的末尾
    if p:
        r.next = p
    if q:
        r.next = q

    return Hc