HJ8 题解 | #合并表记录# 单链表o(n)解法

#include<iostream>
using namespace std;

typedef struct sheet {   //定义链表结点
    int index;
    int value;
    struct sheet* next;
} recSheet, *rS;

int main() {
    int n = 0; // 键值对数量
    recSheet* p = nullptr; // 遍历指针
    recSheet* q = nullptr; // 遍历指针
    rS L = nullptr; // 创建recSheet表
    L = new recSheet; // 创建头节点
    L->index = -1;
    L->value = -1;
    L->next = nullptr;
    cin >> n;
    while (n > 0) {
        recSheet* s = new (recSheet);
        cin >> s->index;
        cin >> s->value;
        p = L->next;
        q = L;
        while (q) { //q初始指向头节点，肯定不为空
            if (p != NULL && p->index == s->index) {  //p可能为空，条件顺序不能错
                p->value += s->value;
                 delete s; //结点不需要插入链表，释放结点空间
                break;
            }


            if (p == NULL || (p->index > s->index)) {  //p可能为空，条件顺序不能错
                s->next = p;
                q->next = s;
                break;
            }

            q = p;
            p = p->next;
        }
        n--;
    }
    p = L->next;
    while (p) {
        cout << p->index << ' ' << p->value << endl;
        p = p->next;
    }
    delete L;  //释放链表空间
    return 0;
}