• 智能AI问答!更聪明、更完整、原创作!
  • 一款基于GPT的超级AI机器人,可以回答问题、聊天、创作、写文案!

用c++将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。

发布于 2024-11-28 22:29:56

为了将两个非递减(升序)的有序链表合并为一个非递增(降序)的有序链表,我们可以采用三个指针遍历的方法来调整链表节点的位置。假设我们使用的是单链表结构,以下是C++代码示例:

#include <iostream>

// 定义单链表的节点结构
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 用于打印链表的辅助函数
void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

// 主函数:合并非递减有序链表,并返回非递增有序链表
ListNode* mergeInReverseTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0);  // 创建假链表头节点,便于操作
    ListNode* tail = dummy;  // 使用尾插法构建新链表

    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1->next = l2;  // 注意这里,需要处理下一个节点的连接
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2->next = l1;  // 同上,处理下一个节点的连接
            l2 = l2->next;
        }
        tail = tail->next;
    }

    // 如果还有剩余节点,需要连接到结果链表尾部
    if (l1 != nullptr) {
        tail->next = l1;
    } else if (l2 != nullptr) {
        tail->next = l2;
    }

    ListNode* newHead = dummy->next;  // 获取新链表的头节点
    delete dummy;  // 删除假链表头节点
    return newHead;
}

int main() {
    // 示例:创建两个链表并进行合并
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(3);
    l1->next->next = new ListNode(5);

    ListNode* l2 = new ListNode(2);
    l2->next = new ListNode(4);
    l2->next->next = new ListNode(6);

    std::cout << "List 1: ";
    printList(l1);
    std::cout << "List 2: ";
    printList(l2);

    ListNode* mergedList = mergeInReverseTwoLists(l1, l2);
    std::cout << "Merged and Reversed List: ";
    printList(mergedList);

    // 记得释放链表内存,避免内存泄露
    while (mergedList != nullptr) {
        ListNode* temp = mergedList;
        mergedList = mergedList->next;
        delete temp;
    }

    return 0;
}

以上代码实现以下功能:

  • 使用 ListNode 结构体定义链表节点。
  • mergeInReverseTwoLists 函数负责合并两个有序链表,并通过调整节点的连接使得合并后的链表为非递增顺序。
  • printList 函数用于打印链表以便验证结果。
  • main 函数中创建两个样例链表,并展示合并效果。

注意,在实际应用中,你需要自己负责释放在程序中创建的所有节点以避免内存泄露。

0 条评论

发布
问题

在线
客服