单链表模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

来看一道题目：

题目链接：1025 反转链表

我没做出来，跪在了反转上，没想到可以用reverse()函数，也没考虑到无效结点的坑，果然还是太菜了。

贴一个大佬的代码：

数组的做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int first, k, n, temp;
    cin >> first >> n >> k;
    int data[100005], next[100005], list[100005];
    for (int i = 0; i < n; i++) {
        cin >> temp;
        cin >> data[temp] >> next[temp];    //以地址为索引存储数据和下一个的地址
    }
    int sum = 0;//不一定所有的输入的结点都是有用的，加个计数器
    while (first != -1) {    //对合理的输入进行计数，并且存起来，筛选掉断开的节点输入
        list[sum++] = first;
        first = next[first];
    }
    for (int i = 0; i < (sum - sum % k); i += k)    //只需要对需要反转的部分反转即可
        reverse(begin(list) + i, begin(list) + i + k);
    for (int i = 0; i < sum - 1; i++)    //输出的时候注意最后一个元素的特殊性
        printf("%05d %d %05d\n", list[i], data[list[i]], list[i + 1]);
    printf("%05d %d -1", list[sum - 1], data[list[sum - 1]]);
    return 0;
}

struct + vector的做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//PAT1025V2 
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct node{
	int address;
	int data;
	int next;
};
int main(){
	int N,first,K,i;
	vector<node> shunxu,reverse;
	cin>>first>>N>>K;
	node n;	//临时节点 
	node addr[100000];	//链表数组
	for(i=0;i<N;i++){
		cin>>n.address>>n.data>>n.next;
		addr[n.address]=n;	//将节点赋值到相应下标的位置 
	} 
	int nextaddress=first;
	while(nextaddress!=-1){	//通过next作为下标寻找元素，添加到vector中，更新next继续寻找
		shunxu.push_back(addr[nextaddress]);
		nextaddress=addr[nextaddress].next ; 
	} 
	int size=shunxu.size();	//输入的节点可能有些不在链表中，记录链表长度
	int tmp=K-1;
	while(tmp<size){	//反转链表，每次翻转K个，不足k个不反转并退出循环
		for(i=tmp;i>tmp-K;i--)	reverse.push_back(shunxu[i]);  //每段内倒过来翻转 
		tmp+=K;
	} 
	for(i=tmp-K+1;i<size;i++) reverse.push_back(shunxu[i]);	//将最后没有反转的，复制到反转之后的链表
	for(i=0;i<size-1;i++){	//修改它们的next ，改为下一个元素的address
		reverse[i].next=reverse[i+1].address;
		printf("%05d %d %05d\n",reverse[i].address,reverse[i].data,reverse[i].next); 
	} 
	printf("%05d %d %d\n",reverse[size-1].address,reverse[size-1].data,-1); 
}