7-2 Rank a Linked List (25 分)_随笔

7-2 Rank a Linked List (25 分) 7-2 Rank a linked List (25 分)

A linked list of n nodes is stored in an array of n elements. Each element contains an integer data and a next pointer which is the array index of the next node. It is guaranteed that the given list is linear – that is, every node, except the first one, has a unique previous node; and every node, except the last one, has a unique next node.

Now let’s number these nodes in order, starting from the first node, by numbers from 1 to n. These numbers are called the ranks of the nodes. Your job is to list their ranks.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive number n (≤105) which is the total number of nodes in the linked list. Then n numbers follow in the next line. The ith number (i=0,⋯,n−1) corresponds to next(i) of the ith element. The NULL pointer is represented by −1. The numbers in a line are separated by spaces.

Output Specification:
List n ranks in a line, where the ith number (i=0,⋯,n−1) corresponds to rank(i) of the ith element. The adjacent numbers in a line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

5
3 -1 4 1 0

Sample Output:

3 5 1 4 2

Hint:

The given linked list is stored as 2->4->0->3->1->NULL. Hence the 0th element is ranked 3 since it is the 3rd node in the list; the 1st element is ranked 5 since it is the last (the 5th) node in the list; and so on so forth.

找到-1的点，从后往前找就行

#include 
#include 
using namespace std;
int a[100100];
map m;
int main() {
	int n, root, ret = 1, x;
	cin >> n;
	for(int i = 0; i < n; ++i) {
		cin >> x;
		m[x] = i;
		if(x == -1)
			root = x;
	}
	while(ret <= n){
		a[m[root]] = ret++;
		root = m[root];
	}
	for(int i = 0; i < n; ++i){
		if(i != 0) cout << " ";
		cout << ret - a[i];
	}
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5691070.html

7-2 Rank a Linked List (25 分)

发表评论

评论列表（0条）