(重要)1133 Splitting A Linked List (怎样把一条链表拆成若干条新链表然后相连)

缺乏、安全感 2022-03-22 03:05 84阅读 0赞

Given a singly linked list, you are supposed to rearrange its elements so that all the negative values appear before all of the non-negatives, and all the values in \[0, K\] appear before all those greater than K. The order of the elements inside each class must not be changed. For example, given the list being 18→7→-4→0→5→-6→10→11→-2 and K being 10, you must output -4→-6→-2→7→0→5→10→18→11.

### 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 (≤105) which is the total number of nodes, and a positive K (≤103). 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 in \[−105,105\], and `Next` is the position of the next node. It is guaranteed that the list is not empty.

### Output Specification: ###

For each case, output in order (from beginning to the end of the list) the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

### Sample Input: ###

00100 9 10
    23333 10 27777
    00000 0 99999
    00100 18 12309
    68237 -6 23333
    33218 -4 00000
    48652 -2 -1
    99999 5 68237
    27777 11 48652
    12309 7 33218

### Sample Output: ###

33218 -4 68237
    68237 -6 48652
    48652 -2 12309
    12309 7 00000
    00000 0 99999
    99999 5 23333
    23333 10 00100
    00100 18 27777
    27777 11 -1

解题思路:

这种题型我们其实不用大费周折地在原链表上拆解链表然后重新相连

我们直接通过vector就可以实现:把满足某些条件的结点地址直接放到对应vector容器中

连接顺序根据题意遍历对应的容器即可

#include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    const int MAXN = 100010;
    const int MAXNUM = 10010;
    struct Node {
    	int data;
    	int nextAddr;
    }nodes[MAXN];
    vector<int> vecs[3];  //存储三种类型的vec
    int main() {
    	int sAddr, N, K;
    	scanf("%d %d %d", &sAddr, &N, &K);
    	for (int i = 0; i < N; ++i) {
    		int Addr, nextAddr, data;
    		scanf("%d %d %d", &Addr, &data, &nextAddr);
    		nodes[Addr].data = data;
    		nodes[Addr].nextAddr = nextAddr;
    	}
    	int p1 = sAddr;
    	while (p1 != -1) {
    		if (nodes[p1].data < 0) vecs[0].push_back(p1);
    		else if (nodes[p1].data > K) vecs[2].push_back(p1);
    		else vecs[1].push_back(p1);
    		p1 = nodes[p1].nextAddr;
    	}
    
    	bool flag = true;
    	int curAddr = -1;
    	for (int i = 0; i < 3; ++i) {
    		for (int j = 0; j < vecs[i].size(); ++j) {
    			if (flag) {
    				printf("%05d %d ", vecs[i][j], nodes[vecs[i][j]]);
    				flag = !flag;
    			}
    			else {
    				curAddr = vecs[i][j];
    				printf("%05d\n%05d %d ", curAddr, vecs[i][j], nodes[vecs[i][j]]);
    			}
    		}
    	}
    	printf("-1");
    	system("PAUSE");
    	return 0;
    }