题目
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
基本思路
使用一个长度为99999的数组存放数据和next指针。最后进行反转。有两种方法:1.另建一个数组,存放要输出的数据,每次遍历反转个数个元素,并按相反顺序填入数组;2.把每个元素的next指针指向上一个元素,最后把原头结点的next指向新头结点的旧next。
代码
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
struct Node
{
int val;
int next;
};
int reverseList(Node a[],int header,int reverse);
int getLength(Node a[],int header);
int main()
{
Node a[100000];
int header, length, reverse=0;
cin >> header;
cin >> length;
cin >> reverse;
for (int i = 0; i < length; i++)
{
int pos;
scanf("%d", &pos);
scanf("%d %d", &a[pos].val, &a[pos].next);
}
int realLength=getLength(a, header);
//反转
int nowPos=header,nowHeader=0,newHeader=header,lastRear=0;
if(reverse>1)
{
for(int i=0;i<realLength/reverse;i++)
{
//第一次反转更新头结点
if(nowPos==header)
{
lastRear=nowPos;
nowHeader=reverseList(a,header,reverse);
newHeader=nowHeader;
nowPos=a[lastRear].next;
}
else
{
nowHeader=reverseList(a,nowPos,reverse);
a[lastRear].next=nowHeader;
lastRear=nowPos;
nowPos=a[lastRear].next;
}
}
}
//输出
int pos=newHeader;
while (pos!=-1)
{
printf("%05d %d ", pos, a[pos].val);
if (a[pos].next!= -1)
printf("%05d\n", a[pos].next);
else
printf("%d\n", a[pos].next);
pos = a[pos].next;
}
return 0;
}
int getLength(Node a[],int header)
{
int pos=header;
int length=0;
while (pos!=-1)
{
length++;
pos = a[pos].next;
}
return length;
}
int reverseList(Node a[],int header,int reverse)
{
int nowP=a[header].next,lastP=header;
//先将第2-reverse间的元素的next指向上一个元素
for(int i=0;i<reverse-1;i++)
{
if(nowP==-1)
break;
int newPos;
newPos=a[nowP].next;
a[nowP].next=lastP;
//更新位置
lastP=nowP;
nowP=newPos;
}
a[header].next=nowP;
header=lastP;
return header;
}
总结
第一次做时还是没审清题意,题目是要每K个元素反转,一开始只反转了一次。还有就是注意调用反转函数次数应该是链表的真实长度/反转长度,因为可能会有多余结点。