博客

问题

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10​5​​) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 6 4

00000 4 99999

00100 1 12309

68237 6 -1

33218 3 00000

99999 5 68237

12309 2 33218

Sample Output:

00000 4 33218

33218 3 12309

12309 2 00100

00100 1 99999

99999 5 68237

68237 6 -1

解决方法

用reverse函数和vector结合，先将节点存入一个vector中，然后进行排序，将排好序的节点存入另外一个vector进行逆转。

code1 4分

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node {int address,data,next;};
int main()
{
	vector<node>v, s;
	node a;
	int firstaddress, n, k;
	cin >> firstaddress >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a.address >> a.data >> a.next;
		v.push_back(a);
	}
	for (auto it = v.begin(); it != v.end(); it++) {
		if (it->address == firstaddress) {
			s.push_back(*it);
		}
	}
	while (s.back().next != -1) {
		for (int i = 0; i < v.size(); i++) {
			if (v[i].address == s.back().next) {
				s.push_back(v[i]);
			}
		}
	}
	for (int i = 0; i < s.size(); i+=k) {if(i+k<=s.size()) reverse(s.begin() + i, s.begin() + i + k);}
	for (int i = 0; i < s.size(); i++) {
			if (s[i].next == -1) printf("%05d %d %d\n", s[i].address, s[i].data, s[i].next);
			else printf("%05d %d %05d\n", s[i].address, s[i].data, s[i].next);
	}
	return 0;
}

 printf("%05d %d %d\n", s[i].address, s[i].data, s[i].next);

这里应该输出s[i+1].address,这个就是错的，因为两个测试点是巧合过的，如果把标准测试案例过了至少能拿一半的分。过了两个测试案例让我产生了一种错觉，这是对的。就是因为这个让我倒腾了一个下午。哭唧唧！

没有仔细核对标准测试案例，马大哈（o(╥﹏╥)o）其实就离正确差最后一步。。。

code2 25分

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node { int address, data, next; };
int main()
{
	vector<node>v, s;
	node a;
	int firstaddress, n, k;
	cin >> firstaddress >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a.address >> a.data >> a.next;
		v.push_back(a);
	}
	for (auto it = v.begin(); it != v.end(); it++) {
		if (it->address == firstaddress) {
			s.push_back(*it);
		}
	}
	while (s.back().next != -1) {
		for (int i = 0; i < v.size(); i++) { 
			if (v[i].address == s.back().next) s.push_back(v[i]); 
		}
	}
	for (int i = 0; i < (s.size() - s.size() % k); i += k) {
		if (i + k <= v.size())reverse(s.begin() + i, s.begin() + i + k); 
	}
	for (int i = 0; i < s.size() - 1; i++) {
		printf("%05d %d %05d\n", s[i].address, s[i].data, s[i + 1].address);	
	}
	printf("%05d %d -1\n", s.back().address, s.back().data);
	return 0;
}

值得注意的地方

1.s.back()最后一个元素的使用

2.细节比如最后一个节点单独输出，如果按照循环那样输出，就会存在数组越界的情况。

3.%5d是为了控制格式

4.

for (int i = 0; i < (s.size() - s.size() % k); i += k) {
		if (i + k <= v.size()){
		reverse(s.begin() + i, s.begin() + i + k); 
		}
	}

 i < (s.size() - s.size() % k);

是为了通测试点6，链表上有多余节点的问题。

后记

链表翻转是一个经典的问题，此题一定要非常熟悉！