pta Reversing Linked List 题解

7-1 Reversing Linked List (25 分)

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

解题思路

题目大意：一共有n个元素，每k个元素作为一组逆置组，每一个逆置组单独逆置，不足k个元素的组不改变顺序。要注意的是输入有可能会有多余的节点要去除 因为每组单独逆置的第一个一定是这组逆置的最后一个，所以标记第一个，然后后面的插在这个节点的前面 设置两个指针ltailp和tailp。ltailp标记的是上一组逆置的第一个，tailp是当前逆置组的第一个 如果这两个指针相同说明只有一组逆置，不同就说明有多组逆置 用ltailp连接本组逆置的最后一个，解决不同逆置组之间相连问题

代码

//7-1 Reversing Linked List #include <stdio.h> #include <stdlib.h> #define N (100000 + 5) typedef struct node{ int data; int cur,nxt; //保存地址 struct node *next; }Node,*List; //原始数据用结构体数组表示，下标表示当前结点的地址 typedef struct dataType{ int data; //数据 int next; //下一个结点地址 }Data; Data dt[N]; //保存N个结点的原始数据 //根据头结点下标first和数据源a创建单链表 List createList(int *n,int first); //逆置含有n个结点的链表head的k个结点 List reverseList(List head,int n,int k); //打印链表，测试用 void printList(List head); int main() { //1.读入数据 int ft,n,k; scanf("%d%d%d",&ft,&n,&k); // printf("%d %d %d\n",ft,n,k); //读入n个结点信息 for(int i = 0;i < n;i++){ //当前结点的地址和下一个结点的地址 //直接按整数处理 int cur,x,nxt; scanf("%d%d%d",&cur,&x,&nxt); dt[cur].data = x; //保存数据 dt[cur].next = nxt; //保存下一个结点下标 } List head = createList(&n,ft); head = reverseList(head,n,k); //逆置 printList(head); //打印 return 0; } //根据头结点下标first和数据源a创建单链表 List createList(int* n,int first) { List head = NULL,tail,p; //表头，表尾，当前结点 int sum = 0; //链表的有效结点数 while(1){ p = (List)malloc(sizeof(Node)); //分配内存 if(head == NULL){ p->cur = first; //结点的当前地址 head = p; } else{ p -> cur = tail->nxt; if(p -> cur == -1){ //表尾 free(p); //释放内存 break; } tail -> next = p; } p->data = dt[p->cur].data; //结点数据 p->nxt = dt[p->cur].next; //结点下一个结点的地址 p->next = NULL; tail = p; //更新表尾 sum++; // printf("d %d d,n = %d\n",tail->cur,tail->data,tail->nxt,n); } *n = sum; return head; } //逆置含有n个结点的链表head的k个结点 List reverseList(List head,int n,int k){ List t=head,q=NULL,tailp=NULL,p=NULL,headp=NULL,ltailp=NULL; for(int i=0;i<n/k;i++){ q=NULL; int temp=k; ltailp=tailp; while(temp--){ p=(List)malloc(sizeof (struct node)); p->data=t->data; p->cur=t->cur; if(q==NULL){ if(i==0){ ltailp=tailp=p; q=p; p->next=NULL; p->nxt=-1; }else { tailp=p; q=p; p->next=NULL; p->nxt=-1; } }else{ p->next=q; p->nxt =q->cur ; q=p; } t=t->next; } if(ltailp!=tailp){ ltailp->next=p; ltailp->nxt =p->cur; } if(!i)headp=p; } if(tailp){ while(t){ tailp->next=t; tailp->nxt=t->cur; tailp=t; t=t->next; } return headp; }else { return head; } } //打印链表，测试用 void printList(List head) { for(List p = head;p;p = p->next){ printf("d %d ",p->cur,p->data); if(p->nxt == -1) //-1直接输出 printf("-1\n"); else printf("d\n",p->nxt); } } /* 00100 6 2 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218 */

还可以用数组模拟链表的实现过程

#include <stdio.h> #include <stdlib.h> #define N 100001 #define HEAD 100000 #define OK 1 #define ERROR 0 typedef int Status; typedef struct Node { int data; int next; }Node; Node L[N]; int Last=HEAD; Status createList(int head,int n); Status reverseList(int k); Status printList(); Status CountNode(int &n); int main() { int head,n,k,m=1; scanf("%d%d%d",&head,&n,&k); createList(head,n); CountNode(n); for(int i=1;i<=n-k+1;i+=k) reverseList(k); printList(); return 0; } Status InitList() { for(int i=0;i<N;i++){ L[i].data=0; L[i].next=-1; } return OK; } Status createList(int head,int n) { InitList(); L[HEAD].next = head; int ads,da,nxt; for(int i=0;i<n;i++){ scanf("%d%d%d",&ads,&da,&nxt); L[ads].data=da; L[ads].next=nxt; } } Status CountNode(int &n) { int p = HEAD; n=0; while(L[p].next != -1){ p=L[p].next; n++; } return OK; } Status reverseList(int k) { int p = Last; int q = Last; Last = L[p].next; for(int i=1;i<=k;i++) q = L[q].next; for(int i=1;i<=k-1;i++){ int temp=L[p].next; L[p].next = L[temp].next; L[temp].next = L[q].next; L[q].next = temp; } return OK; } Status printList() { int p = L[HEAD].next; while(L[p].next!=-1){ printf("d %d d\n",p,L[p].data,L[p].next); p = L[p].next; } printf("d %d %d\n",p,L[p].data,L[p].next); return OK; }