练习题 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递增次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

可以使用双指针法，分别指向两个链表的头结点，比较两个结点的值，将较小的结点加入新链表中，并将指针向后移动。直到其中一个链表为空，将另一个链表剩余的结点加入新链表中即可。

以下是示例代码：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return dummy->next;
}

相关问题

假设有两个按元素值递增次序排列的线性表，均以单链表形式存储，请编写程序将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表

为了合并两个已排序的递增单链表并得到一个递减的单链表，你可以按照以下步骤编写程序：

1. 创建一个新的头节点 `new_head` 和空指针 `prev`, 用于存放当前最低元素的新节点。

2. 遍历两个输入链表 `list1` 和 `list2` 的首节点 (`node1` 和 `node2`)，比较它们的值：

- 如果 `node1` 的值小于等于 `node2` 的值，将其添加到新链表中，并更新 `prev` 和 `node1` 作为下一个遍历的节点。
- 否则，将 `node2` 添加到新链表中，并更新 `prev` 和 `node2`。

3. 当其中一个链表遍历完后，将另一个剩余链表中的所有节点依次添加到新链表的末尾。

4. 将 `prev` 指向的节点设为新的头节点 `new_head`。

以下是这个过程的伪代码示例：

def merge_sorted_lists(list1_head, list2_head):
    new_head = None
    prev = None

    while list1_head and list2_head:
        if list1_head.value <= list2_head.value:
            if not new_head:
                new_head = list1_head
            prev.next = list1_head
            list1_head = list1_head.next
        else:
            if not new_head:
                new_head = list2_head
            prev.next = list2_head
            list2_head = list2_head.next

        prev = prev.next

    # 如果还有剩余的链表，直接添加到新链表
    if list1_head:
        prev.next = list1_head
    elif list2_head:
        prev.next = list2_head

    return new_head

假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

要合并两个按元素值递增排序的单链表，得到一个按元素值递减排序的新链表，同时保持原有的节点结构，可以采用以下步骤：

1. 创建一个新的头节点`newHead`，用于存放合并后的链表。

2. 初始化两个指针`p1`和`p2`分别指向两个输入链表的头部。

3. 当`p1`和`p2`都不为空时，比较它们当前节点的值。取较小的节点（即当前元素较大的那个），将其添加到新链表`newHead`的后面，并移动该节点到原链表的下一个节点。如果`p1`的值小于`p2`，则更新`p1`；反之，更新`p2`。

4. 当其中一个指针到达链表末尾时，将另一个剩余的链表剩余部分直接接到新链表的尾部。

5. 最终，返回新的头节点`newHead`，它就是按照元素值递减顺序排列的合并链表。

以下是这个过程的伪代码示例：

def merge_sorted_lists(list1_head, list2_head):
    new_head = ListNode(0)  # 创建新链表的头节点
    current = new_head
    
    while p1 and p2:
        if p1.val > p2.val:  # 如果p1的值较大，选择p2并链接
            current.next = p2
            p2 = p2.next
        else:  # 否则选择p1并链接
            current.next = p1
            p1 = p1.next
            
    if p1:  # 将未遍历完的链表连接到新链表末尾
        current.next = p1
    elif p2:  # 同理处理第二个链表
        current.next = p2
        
    return new_head