二、头指针型单链表 俩个升序表合成降序表合并成降序

### 回答1：
头指针型单链表是一种常见的链表结构，在链表开头添加一个头指针，用于指向链表中第一个节点。在这种链表结构中，空链表的头指针指向 NULL。

以下是将两个升序表合成降序表的算法：

// 头指针型单链表结构体
struct Node {
    int val;
    Node* next;
};

// 合并两个升序表为一个降序表
Node* mergeDescending(Node* head1, Node* head2) {
    Node* mergedHead = new Node();  // 创建一个新链表头指针
    mergedHead->next = NULL;
    Node* pre = mergedHead;   // 指向新链表中前一个节点
    
    // 从头到尾遍历链表1和链表2
    while (head1 != NULL && head2 != NULL) {
        if (head1->val >= head2->val) {  // 如果链表1当前节点的值比链表2小
            pre->next = head1;   // 将链表1当前节点接在新链表中前一个节点后面
            head1 = head1->next; // 链表1指针后移
        } else {  // 如果链表2当前节点的值比链表1小
            pre->next = head2;   // 将链表2当前节点接在新链表中前一个节点后面
            head2 = head2->next; // 链表2指针后移
        }
        pre = pre->next;  // 新链表指针后移
    }
    
    // 将剩下的链表1或链表2直接接到新链表中
    if (head1 != NULL) {
        pre->next = head1;
    } else {
        pre->next = head2;
    }
    
    // 将新链表反转并返回
    Node* cur = mergedHead->next;
    mergedHead->next = NULL;
    while (cur != NULL) {
        Node* temp = cur->next;
        cur->next = mergedHead->next;
        mergedHead->next = cur;
        cur = temp;
    }
    delete mergedHead;
    return mergedHead->next;
}

在这个算法中，我们首先创建了一个新的头指针型单链表，用于存储合成的降序表。然后，我们从头到尾遍历了两个升序表，并按照从大到小的顺序将其合并到新链表中。最后，我们将新链表反转并返回。

需要注意的是，我们在合并链表时，每次都将当前最小的节点接在新链表中前一个节点的后面。由于新链表是按照从大到小的顺序排列的，因此每次接入新节点时，我们需要将其接在头节点的后面，因为头节点肯定是最大的。

以下是一个完整的示例：

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
};

void printLinkedList(Node* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

Node* mergeDescending(Node* head1, Node* head2) {
    Node* mergedHead = new Node();
    mergedHead->next = NULL;
    Node* pre = mergedHead;
    while (head1 != NULL && head2 != NULL) {
        if (head1->val >= head2->val) {
            pre->next = head1;
            head1 = head1->next;
        } else {
            pre->next = head2;
            head2 = head2->next;
        }
        pre = pre->next;
    }
    if (head1 != NULL) {
        pre->next = head1;
    } else {
        pre->next = head2;
    }
    Node* cur = mergedHead->next;
    mergedHead->next = NULL;
    while (cur != NULL) {
        Node* temp = cur->next;
        cur->next = mergedHead->next;
        mergedHead->next = cur;
        cur = temp;
    }
    delete mergedHead;
    return mergedHead->next;
}

int main() {
    // 创建两个升序链表
    Node* head1 = new Node();
    head1->next = NULL;
    Node* cur1 = head1;
    for (int i = 1; i <= 5; i++) {
        Node* node = new Node();
        node->val = i * 2;
        node->next = NULL;
        cur1->next = node;
        cur1 = node;
    }
    Node* head2 = new Node();
    head2->next = NULL;
    Node* cur2 = head2;
    for (int i = 1; i <= 3; i++) {
        Node* node = new Node();
        node->val = i * 3;
        node->next = NULL;
        cur2->next = node;
        cur2 = node;
    }
    
    cout << "链表1: ";
    printLinkedList(head1->next);
    cout << "链表2: ";
    printLinkedList(head2->next);
    
    // 将两个升序链表合成降序链表
    Node* mergedHead = mergeDescending(head1->next, head2->next);
    
    cout << "合成降序链表: ";
    printLinkedList(mergedHead);
    
    return 0;
}

输出结果为：

链表1: 2 4 6 8 10 
链表2: 3 6 9 
合成降序链表: 10 9 8 6 6 4 3 2

### 回答2：
头指针型单链表是一种常见的数据结构，它由多个节点组成，每个节点包含一个元素和一个指向下一个节点的指针。对于两个升序表合成降序表的问题，我们可以采取以下步骤进行解决：

1. 创建一个新的头指针节点，将它的next指针指向第一个升序表的头指针节点；

2. 定义两个指针变量p1和p2，分别指向第一个升序表的头指针节点和第二个升序表的头指针节点；

3. 创建一个新的头指针节点dummy，用来指向合并后降序表的头节点；

4. 循环遍历两个升序表，比较p1和p2节点的元素大小，将较大值的节点插入到dummy的后面，并将相应指针后移；

5. 当其中一个升序表遍历完毕后，将另一个升序表剩余部分直接插入到dummy的后面；

6. 返回dummy的next指针，即为合并后的降序表的头节点。

通过以上步骤，我们可以将两个升序表合并成降序表。具体实现时，我们需要注意边界条件和指针的移动，确保遍历完整个链表并正确连接每个节点。

### 回答3：
要将两个升序链表合并成一个降序链表，首先要了解头指针型单链表的特点。头指针型单链表是以头指针为起点的链表，头指针存储的是链表的第一个节点的地址，链表最后一个节点的指针域为NULL。

想要合并两个升序表，我们可以创建一个新的链表，然后从两个升序表的头开始比较节点的值。每次比较两个节点，将较小的节点插入新链表的头部，并将指针指向下一节点。接着再次比较剩余的节点，重复以上步骤，直到其中一个链表为空。

当其中一个链表为空时，代表该链表的所有节点已都插入到新链表中，我们只需将另一个链表剩余的节点依次插入到新链表头部即可。

最后，新链表中的节点已经按照降序排序，我们只需将新链表的头指针修改为新链表的第一个节点的地址，即可完成合并。

通过以上步骤，我们可以将上述两个升序表合并成一个降序表。合并过程中，时间复杂度为O(n+m)，其中n和m分别代表两个升序表的长度。