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

/* 节点结构体，表示多项式的一项 */
struct Node{
    int val;           // 系数
    int exp;           // 指数
    struct Node* next; // 指向下一项
};

/*
 * 函数名：creatlist
 * 功能：创建一个按指数升序排列的多项式链表
 * 参数：
 *     head - 链表头指针（初始为 NULL）
 *     n    - 需要输入的项数
 * 返回值：
 *     创建好的链表头指针
 */
struct Node* creatlist(Node* head, int n){
    for(int i = 1; i <= n; i++){
    	// 分配新节点
        struct Node* tmp = (struct Node*)malloc(sizeof(struct Node)); 
        tmp->next = NULL;
        printf("请输入第%d项的系数和指数： ",i);
        scanf("%d %d", &tmp->val, &tmp->exp);
        
        if(head == NULL){
            // 第一个节点直接作为头节点
            head = tmp;
        } else {
            struct Node* cur = head;
            struct Node* pre = head;
            bool find = false; // 用于标记是否插入完成
            // 找到插入位置，保持指数升序
            while(cur){
                if(cur->exp > tmp->exp){
                    if(cur == head){
                        // 插到头部
                        head = tmp;
                        tmp->next = cur;
                    } else {
                        // 插到中间
                        pre->next = tmp;
                        tmp->next = cur;
                    }
                    find = true;
                    break;
                }
                pre = cur;
                cur = cur->next;
            }
            if(!find){
                // 没有找到比它大的指数，插到末尾
                pre->next = tmp;
            }
        }
    }
    return head;
}

/*
 * 函数名：addtwolist
 * 功能：将两个有序多项式链表相加，生成一个新的有序多项式链表
 * 参数：
 *     head1 - 第一个多项式链表头
 *     head2 - 第二个多项式链表头
 * 返回值：
 *     结果多项式链表头指针
 */
struct Node* addtwolist(Node* head1, Node* head2){
    struct Node* h3 = NULL;  // 结果链表头
    struct Node* cur = h3;   // 指向结果链表末尾
    
    while(head1 && head2){
        struct Node * tmp = (struct Node*)malloc(sizeof(struct Node)); // 分配新节点
        tmp->next = NULL;
        
        if(head1->exp == head2->exp){
            // 指数相同，系数相加
            tmp->val = head1->val + head2->val;
            tmp->exp = head1->exp;
            
            if(h3 == NULL){
                h3 = tmp;
                cur = tmp;
            } else {
                cur->next = tmp;
                cur = cur->next;
            }
            
            head1 = head1->next;
            head2 = head2->next; 
        } 
        else if(head1->exp < head2->exp){
            // head1 指数小，直接拷贝
            tmp->val = head1->val;
            tmp->exp = head1->exp;
            
            if(h3 == NULL){
                h3 = tmp;
                cur = tmp;
            } else {
                cur->next = tmp;
                cur = cur->next;
            }
            
            head1 = head1->next;
        } 
        else {
            // head2 指数小，直接拷贝
            tmp->val = head2->val;
            tmp->exp = head2->exp;
            
            if(h3 == NULL){
                h3 = tmp;
                cur = tmp;
            } else {
                cur->next = tmp;
                cur = cur->next;
            }
            
            head2 = head2->next;
        }
    }
    if(cur == NULL){
        return NULL; // 两个链表都为空
    }
    // 拼接剩余节点
    if(head1) {
        cur->next = head1;
    }
    if(head2){
        cur->next = head2;
    }
    return h3;
}

/*
 * 函数名：printlist
 * 功能：输出多项式链表
 * 参数：
 *     head - 链表头
 * 返回值：无
 */
void printlist(struct Node* head){
    while(head){
        if(head->next == NULL){
            printf("%dx^%d\n", head->val, head->exp);
            break;
        }
        printf("%dx^%d+", head->val, head->exp);
        head = head->next;
    }
}

int main()
{
    int n1 = 0, n2 = 0;
    printf("请输入第一个多项式的项数：\n"); 
    scanf("%d", &n1);
    struct Node* h1 = NULL;
    h1 = creatlist(h1, n1);
    printf("请输入第二个多项式的项数：\n"); 
    scanf("%d", &n2);
    struct Node* h2 = NULL;
    h2 = creatlist(h2, n2);
    struct Node* h3 = NULL;
    h3 = addtwolist(h1, h2);
    printlist(h3);
    return 0;
}

/*
测试数据:
3
2 1
5 3
2 4
2
2 5
3 4
*/