2つの方法でReversing Linked Listを解く

3321 ワード

問題の説明:陳越から
作成者
CHEN, Yue
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

検索:
法一:チェーンテーブルの方法:
#include #include using namespace std; typedef struct node {int Data;int address;int address_next;struct node* next; }Node; Node *p; int main(){int str,num,k;int Adr[10001],NextAdr[100001],data[10001];Node*p,*head,*tmp 1;head=(Node*)malloc(sizeof(node);//ノードを使用して、チェーンテーブルは必ずノード空間を申請しなければならないことを覚えておいてくださいtmp=(Node*)malloc(sizeof(node));//ノードを使用すると、チェーンテーブルは必ずノード空間を申請しなければならないことを覚えておいてくださいcin>>str>>num>>k;tmp=head->next;//p is a empty head nodetmp->address=str;///////////////////////////以下に入力されたデータを、1つのチェーンテーブル////////////////for(int i=0;i{cin>>Adr[i]>>data[i]>>Next Adr[i])に変換する.for(int i=0;i{//coutaddress){tmp->Data=data[i];tmp->address_next=NextAdr[i];}}while(tmp->address_next!=-1){for(int i=0;i{//coutaddress_next){tmp1=(Node*)malloc(sizeof(node));tmp1->address=Adr[i];tmp1->Data=data[i];tmp1->address_next=NextAdr[i];tmp->next=tmp1;tmp=tmp->next;}}}//while(head)//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////Node*new 1、*old、*tmp 2、*tmp 3;//チェーンテーブル反転int n(1);tmp3=head;new1=head->next;old=new1->next;//tmp2=old->next;while(n{tmp2=old->next;old->next=new1;new1=old;old=tmp2;tmp2=tmp2->next;n++;}head->next->next=old;head->next=new1;head=head->next;while(head){//coutnext;}return 0; } 法二:配列、関数を採用する
#include #include using namespace std; int main() {int list[100010];//int address[100010];int node[100010][2];int num,str,k;int address,data,next;cin>>str>>num>>k;for (int i = 0; i < num;++i){cin>>address>>data>>next;node[address][0]=data;node[address][1]=next;//list[i]=address;}int m(0),n=str;while(n!=-1){list[m]=n;m=m+1;n=node[n][1];}for(int j=0;jcout