【算法设计题】合并两个非递减有序链表，第1题（C/C++）

2024-08-05 08:34:02 浏览数 (1)

第1题 合并两个非递减有序链表

已知带头节点的单链表 LA 和 LB ，其元素均为非递减有序排列，编写算法利用原表结点空间，将链表 LA 和 LB 合并为非递减有序序列的单链表 LC

得分点（必背）
代码语言：javascript复制
// 合并两个非递减有序链表（得分点）
LinkList mergeLists(LinkList lista, LinkList listb){
    LinkList listc, p = lista, q = listb, r;
//listc指向lista 和 listb所指结点中较小者
//初始化合并链表的头节点
    if(lista->data<=listb->data){
        listc=lista;
        r=lista;
        p=lista->next;
    }
    else{
        listc=listb;
        r=listb;
        q=listb->next;
    }
//合并两个链表
    while(p!=NULL && q!=NULL){
        if(p->data<=q->data){
            r->next=p;
            r=p;
            p=p->next;
        }
        else{
            r->next=q;
            r=q;
            q=q->next;
        }
    }
    r->next=(p!=NULL)?p:q; //处理剩余节点
    return listc; //返回合并后的链表
}
题解

这段代码的功能是将两个非递减有序链表合并成一个非递减有序链表。下面我将逐步解释这段代码：

函数声明与初始化变量：
代码语言：javascript复制
LinkList mergeLists(LinkList lista, LinkList listb){
    LinkList listc, p = lista, q = listb, r;
  • LinkList mergeLists(LinkList lista, LinkList listb)：函数名为mergeLists，参数是两个非递减有序链表lista和listb，返回值是合并后的链表。
  • LinkList listc, p = lista, q = listb, r;：定义了四个指针变量：
    • listc：用于指向合并后的链表的头节点。
    • p：初始化为指向链表lista的当前节点。
    • q：初始化为指向链表listb的当前节点。
    • r：用于构建合并后的链表。
初始化合并链表的头节点：
代码语言：javascript复制
if(lista->data<=listb->data){
    listc=lista;
    r=lista;
    p=lista->next;
}
else{
    listc=listb;
    r=listb;
    q=listb->next;
}

if(lista->data<=listb->data)：比较lista和listb的头节点数据。

  • 如果lista的头节点数据小于等于listb的头节点数据：
    • listc = lista：将合并链表的头节点指向lista的头节点。
    • r = lista：r指向当前合并链表的最后一个节点（此时是lista的头节点）。
    • p = lista->next：将指针p移动到lista的下一个节点。
  • 否则：
    • listc = listb：将合并链表的头节点指向listb的头节点。
    • r = listb：r指向当前合并链表的最后一个节点（此时是listb的头节点）。
    • q = listb->next：将指针q移动到listb的下一个节点。
合并两个链表：
代码语言：javascript复制
while(p!=NULL && q!=NULL){
    if(p->data<=q->data){
        r->next=p;
        r=p;
        p=p->next;
    }
    else{
        r->next=q;
        r=q;
        q=q->next;
    }
}

while(p!=NULL && q!=NULL)：循环遍历lista和listb，直到其中一个链表遍历完（p或q变为NULL）。

  • if(p->data<=q->data)：比较p和q指向的节点数据。
    • 如果p的数据小于等于q的数据：
      • r->next=p：将当前合并链表的最后一个节点的next指针指向p。
      • r=p：将r指向p，即更新当前合并链表的最后一个节点。
      • p=p->next：将指针p移动到lista的下一个节点。
    • 否则：
      • r->next=q：将当前合并链表的最后一个节点的next指针指向q。
      • r=q：将r指向q，即更新当前合并链表的最后一个节点。
      • q=q->next：将指针q移动到listb的下一个节点。
处理剩余节点：
代码语言：javascript复制
r->next=(p!=NULL)?p:q;

r->next=(p!=NULL)?p:q;：当while循环结束时，可能还剩下一个链表中有未处理完的节点。

  • 如果p不为空，则将r->next指向p，即将剩余的lista节点连接到合并链表的末尾。
  • 如果p为空，则将r->next指向q，即将剩余的listb节点连接到合并链表的末尾。
返回合并后的链表：
代码语言：javascript复制
return listc;
  • return listc;：返回合并后的链表listc。

总结：这段代码通过比较两个链表的节点数据，将较小的数据节点依次连接到合并后的链表中，最终返回一个合并后的非递减有序链表。

完整测试代码
代码语言：javascript复制
#include<iostream>
using namespace std;

// 定义链表节点结构
struct Node {
int data;
Node* next;
};
// 定义 LinkList 类型为指向 Node 的指针
typedef Node* LinkList;
// 初始化链表
void InitList(LinkList& L){
    L=new Node;
    L->next=NULL;
}
// 合并两个非递减有序链表（得分点）
LinkList mergeLists(LinkList lista, LinkList listb){
    LinkList listc, p = lista, q = listb, r;
    //lilistc指向lista 和 listb所指结点中较小者
    if(lista->data<=listb->data){
        listc=lista;
        r=lista;
        p=lista->next;
    }
    else{
        listc=listb;
        r=listb;
        q=listb->next;
    }

    while(p!=NULL && q!=NULL){
        if(p->data<=q->data){
            r->next=p;
            r=p;
            p=p->next;
        }
        else{
            r->next=q;
            r=q;
            q=q->next;
        }
    }
    r->next=(p!=NULL)?p:q;
    return listc;
}
// 打印链表
void printList(LinkList head) {
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // 创建链表 a: 1 -> 3 -> 5
    Node* a1 = new Node{1, nullptr};
    Node* a2 = new Node{3, nullptr};
    Node* a3 = new Node{5, nullptr};
    a1->next = a2;
    a2->next = a3;

    // 创建链表 b: 2 -> 4 -> 6
    Node* b1 = new Node{2, nullptr};
    Node* b2 = new Node{4, nullptr};
    Node* b3 = new Node{6, nullptr};
    b1->next = b2;
    b2->next = b3;

    // 合并链表
    LinkList mergedList = mergeLists(a1, b1);

    // 打印结果
    printList(mergedList); // 应该输出: 1 2 3 4 5 6

    // 清理内存
    while (mergedList != nullptr) {
        Node* temp = mergedList;
        mergedList = mergedList->next;
        delete temp;
    }

    return 0;
}
c++ 链表 设计 算法 指针

0 人点赞