[数据结构与算法]1110 区块反转 (25 分)

题目

题目链接

题解

链表。

我定义的四个指针如下：

目标是将灰色区域移到链表最前端。

实现一下上面灰色区域移到最前端的过程：

先让p的next指针指向tmp的下一个节点，再让tmp的next指针指向链表的起点，最后更新起点为t指针。（顺序不可变）

下面是特殊的最后一块的处理方法：

和上面的思路一致，只不过需要控制t和tmp指针的移动距离。

链表题我感觉我都像是蒙过的。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

struct Node {
	int val, ne;
} node[N];

int main()
{
	int st, n, k;
	cin >> st >> n >> k;
	for (int i = 0;i < n;i ++) {
		int ad, val, ne;
		cin >> ad >> val >> ne;
		node[ad].val = val;
		node[ad].ne = ne;
	} 
	
	int p = st;
	for (int i = 1;i < k && ~node[p].ne;i ++) p = node[p].ne;
	while (~node[p].ne) {
		int t = node[p].ne;
		int tmp = p;
		for (int i = 0;i < k && ~node[tmp].ne;i ++) tmp = node[tmp].ne;
		
		node[p].ne = node[tmp].ne;
		node[tmp].ne = st;
		st = t;
	}
	
	p = st;
	while (~p) {
		printf ("%05d %d ", p, node[p].val);
		if (~node[p].ne) printf ("%05d\n", node[p].ne);
		else cout << node[p].ne << endl;
		p = node[p].ne;
	}
	
	return 0;
}