标签：head 第三节 h2 h1 value next 链表 数据结构

三、数据结构第三节——链表

今天学链表~~~

话不多说，上例题！

---

一、小学生排序

期末考试结束了，老师想请你帮忙统计全班同学的分数。已知班里有 n 个同学，老师会把 n 个同学的分数告诉你，请你按照从小到大的顺序输出全班同学的成绩。保证同学们的分数都是不重复的。

输入格式

第一行，一个整数 n。

接下来 n 行，每行一个 0−1000−100 之间的整数，表示分数。

输出格式

一行 n 个整数，表示答案。

样例输入

3
86
98
61

样例输出

61 86 98

数据限制

对于 100%100% 的数据，保证 1≤n≤80。

---

提交

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int value;
    Node *next;
}a[81], *head;
int n;
int main()
{

    //head = NULL;
    scanf("%d", &n);
    for( int i = 1; i <= n; i++ ){
        scanf("%d", &a[i].value);
        if (  head == NULL  ){
            a[i].next = head;
            head = &a[i];
        }else if ( a[i].value < head -> value  ){
            a[i].next = head;
            head = &a[i];
        }else {
             for ( Node* p = head; p ; p = p -> next ){
                 if (  p -> value < a[i].value  && ( p -> next == NULL || a[i].value < p ->next ->value )){
                     a[i].next = p -> next;
                     p -> next = &a[i];
                     break;
                 }
             }
        }
    }

    for ( Node* p = head; p ; p = p -> next ){
        printf("%d\n",p->value);
    }

//    return 0;
}

另外，15-20行可以可以由以下代码代替

        if (  head == NULL || a[i].value < head -> value  ){
            a[i].next = head;
            head = &a[i];
        }

ps: head == NULL和a[i].value < head -> value的顺序不可以交换！！！

因为两者具有先后顺序，（不会有人在这边debug几个小时吧......）

首先判断链表是否为空（即第一次操作），此时加入head.

在链表不为空的基础上，才可以进行下一步判断，

即：插入元素是否小于head

若小于，则从头部插入；否则，则进行下一步操作。

---

二、合并链表

给你两个有序数列，他们的长度分别为 n和 m，现在需要你完成以下操作：

• 读入这两个数列并用两个链表把他们按从小到大的顺序分别储存下来，生成两个链表的头指针 Node *h1, *h2；
• 编写一个链表合并函数，将两个有序链表合并成一个有序链表。传入的参数为两个待合并链表的头指针，返回值为生成链表的头指针 Node *Merge(Node *h1, *h2)；
• 最后将合并完的链表中的值按从小到大的顺序输出。

输入格式

输入第一行两个整数 n,m。

接下来两行分别是两个长度为 n 和 m 的有序数列。

输出格式

输出一行表示答案。

样例输入

4 3
1 2 3 5
2 4 6

样例输出

1 2 2 3 4 5 6

数据规模

对于所有数据，保证 1≤n,m≤100000。

提交

#include <bits/stdc++.h>
using namespace std;
const int N =100000;
struct Node{
    int value;
    Node* next;
}*h1, *h2, *t1, *t2, a[N+10], b[N+10];
//创建链表，同时定义全局自动初始化head和tail为NAULL.
int n,m;

Node *Merge(Node *h1, Node *h2 ){
    Node *h = NULL , *t = NULL;
    while( h1 || h2 ){
        if ( h1 && ( h2 == NULL || h1 -> value < h2 -> value ) ){
            if ( h == NULL ){
                h = h1;
                t = h1;
            } else {
                t -> next = h1;
                t = h1;
            }
            h1 = h1 -> next;
        }

        else{
            if ( h == NULL ){
                h = h2;
                t = h2;
            }else{
                t -> next = h2;
                t = h2;
            }
            h2 = h2 -> next;
        }
	}
 return h;
}

int main()
{
    scanf("%d %d", &n, &m);
    for( int i = 1; i <= n; i++ ){ //读入链表 1
        scanf("%d", &a[i].value ); //读入数据
        if ( h1 == NULL ){       //首先判断链表是否为空（是否为第一次操作，   //则插入头部
            h1 = &a[i];          //若为第一次（即链表内只有一个节点，则head和tail均为 a[i])
            t1 = &a[i];
        }else{                   //若链表不空，即不是第一次操作，           //则插入尾部
            t1 -> next = &a[i];  //连接插入节点
            t1 = &a[i];          //更新tail 1
        }
    }

    ///同理 读入链表2
    for( int i = 1; i <= m; i++ ){ //读入链表 2
        scanf("%d", &b[i].value ); //读入数据
        if ( h2 == NULL ){       //首先判断链表是否为空（是否为第一次操作，   //则插入头部
            h2 = &b[i];          //若为第一次（即链表内只有一个节点，则head和tail均为 b[i])
            t2 = &b[i];
        }else{                   //若链表不空，即不是第一次操作，           //则插入尾部
            t2 -> next = &b[i];  //连接插入节点
            t2 = &b[i];          //更新tail 2
        }
    }

    Node* p = Merge( h1, h2);
    for ( ; p ; p = p -> next ){
        printf("%d ", p-> value);
    }

    return 0;
}

写完一定要检查括号位置！！！（因为括号而debug了几个小时的大怨种......）

---

awsl，写不下去了，第二题盯着电脑屏幕debug了几个小时，输在了一个括号，救命T_T

感慨：学算法比起费脑子，更废眼睛T_T 眼睛好疼...

标签：head,第三节,h2,h1,value,next,链表,数据结构
From： https://www.cnblogs.com/XTian258/p/17004708.html