02 - 선형 구조 2 리 버스 링 링크 목록
Reversing Linked List (25 분)
Given a constant KK and a singly linked list LL, you are supposed to reverse the links of every KK elements on LL. For example, given LL being 1→2→3→4→5→6, if K = 3K=3, then you must output 3→2→1→6→5→4; if K = 4K=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 NN (\le 10^5≤105) which is the total number of nodes, and a positive KK (\le N≤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 NN 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
#define MAXSIZE 100001 //100001=100000+1
typedef struct LNode *Ptr;
struct LNode{
int address;
int data;
int next;
Ptr link; //
}list;
Ptr Reverse(Ptr head, int K,int L);
Ptr MakeList(int f_add, int next_add[],int data[],int L);
void Attach(int a,int n_a,int data,Ptr *pRear);
void PrintList(Ptr P);
int main()
{
int K = 0, L = 0; //K ,L
int link_num = 0;//
int i;//
int address_tmp;//
int first_add;//
Ptr p,p_tmp,r_p;
int Next[MAXSIZE] ;// address
int Data[MAXSIZE] ;// address
// , ,
scanf("%d %d %d",&first_add,&L,&K);
//
for(i = 0 ; i < L ; i++){
scanf("%d",&address_tmp);//
scanf("%d %d",&Data[address_tmp],&Next[address_tmp]);
}
//
p = MakeList(first_add,Next,Data,L);
// ****************** *****************************
if(K<=L){//K<=L
for(i = 0; i < (L/K); i++){
r_p = Reverse(p,K,L);
p_tmp ->link = r_p;//
p_tmp ->next = r_p->address;
for(int j = 0; j < K; j++ ){
// p ( )
p_tmp = p_tmp->link;
}
}
}
//************************************************************
//
PrintList(p_tmp);
return 0;
}
Ptr MakeList(int f_add, int next_add[],int data[],int L)
{
Ptr P , Rear, t;
int t_L = L;
int a,n_a,d,tmp_n_a;
int i;
P = (Ptr)malloc(sizeof(struct LNode));//
P->link = NULL;
Rear = P;
//
a = f_add;
d = data[a];
n_a = next_add[a];
Attach(a,n_a,d,&Rear);
t_L--;
while(t_L--){//
a = n_a;
d = data[a];
n_a = next_add[a];
Attach(a,n_a,d,&Rear);
}
//t = P;P=P->link;free(t);//
return P;
}
void Attach(int a,int n_a,int data,Ptr *pRear)
{
Ptr P;
P = (Ptr)malloc(sizeof(struct LNode));
P->address = a;
P->data = data;
P->next = n_a;
P->link = NULL;
(*pRear)->link = P;
*pRear = P;
}
Ptr Reverse(Ptr head, int K,int L)
{
int cnt = 1;
Ptr new_, old,tmp;
// new_, ,new_ = head->link;
new_ = head->link;
// old, old = new_->link;
old = new_->link;
while(cnt < K){
// tmp, old ,tmp = old->link;
tmp = old->link;
// old new_, old->link = new_;
old->link =new_;
//old new_
old->next = new_->address;
// ,old new_ new_,
// old new_,new_ = old;
new_ = old;
// old tmp,old = tmp;
old = tmp;
cnt ++;
}
///
head->link->link = old;
if(old != NULL){//
head->link->next = old -> address;
}
else{
head->link->next = -1;//
}
return new_;
}
void PrintList(Ptr P)
{
while(P){
if(P->next == -1) {//
printf("%.5d %d %d
",P->address,P->data,P->next);
}
else{
printf("%.5d %d %.5d
",P->address,P->data,P->next);
// ,%.5 5 , 0 :22, :00022
}
P = P->link;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
02 - 선형 구조 2 리 버스 링 링크 목록02 - 선형 구조 2 Reversing Linked List (25 분) Given a constant KK and a singly linked list LL, you are supposed to reverse ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.