题解 | #合并表记录#单向链接插入时排序

#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
    int index;
    int value;
    struct Node* next;
} NodeLink;

NodeLink* init_node(int index, int value)
{
    NodeLink *p = (NodeLink *)malloc(sizeof(NodeLink));
    p->index = index;
    p->value = value;
    p->next = NULL;
    return p;
}

NodeLink* insert_and_sort(NodeLink *head, int index, int value)
{
    NodeLink *cur = head;
    NodeLink *pre = head;
    
    if (head == NULL) {
        head = init_node(index, value);
        head->next = NULL;
        return head;
    }

    while (cur) {
        if (index == cur->index) {
            cur->value += value;
            return head;
        } else if (index < cur->index) {
            NodeLink* p = init_node(index, value);
            p->next = cur;
            if (cur != head) {
                pre->next = p;
            } else {
                head = p;
            }
            return head;
        } else {
            if (cur->next == NULL) {
                NodeLink* p = init_node(index, value);
                cur->next = p;
                return head;
            } else {
                pre = cur;
                cur = cur->next;
            }
        }
    }
    return head;
}

void free_link(NodeLink *head)
{
    NodeLink *cur = head;
    while (cur) {
        NodeLink *tmp = cur;
        cur = cur->next;
        free(tmp);
    }
}

void show_link(NodeLink *head)
{
    NodeLink *cur = head;
    while (cur) {
        printf("%d %d\n", cur->index, cur->value);
        cur = cur->next;
    }
}

int main() {
    NodeLink *head = NULL;
    int key, value;
    int max = 0;
    scanf("%d", &max);

    while (scanf("%d %d", &key, &value) != EOF) {
        head = insert_and_sort(head, key, value);
    }

    show_link(head);
    free_link(head);
    return 0;
}