Description
给定一个常数 K 以及一个单链表 L,请编写程序将 L 中每 K 个结点反转。例如:给定 L 为 1*2*3*4*5*6,K 为 3,则输出应该为 3*2*1*6*5*4;如果 K 为 4,则输出应该为 4*3*2*1*5*6,即最后不到 K 个元素不反转。
Input
每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤10 5 )、以及正整数 K (≤N),即要求反转的子链结点的个数。结点的地址是 5 位非负整数,NULL 地址用 −1 表示。 接下来有 N 行,每行格式为:
Output
对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。
参考程序1(Python语言)
def CreateList(dic,firstadd):
ls=[]
while firstadd!="-1":
ls.append(dic[firstadd])
firstadd=dic[firstadd][2]
return ls
def K_reverse(ls,K):
i=0
number=[]
while i+K<=len(ls):
left=ls[i:i+K]
number+=list(reversed(left))
i+=K
number+=ls[i:]
for i in range(len(number)-1):
number[i][2]=number[i+1][0]
number[-1][2]=-1
return number
first_add,node_amount,K=input().split()
node_amount=int(node_amount)
K=int(K)
list_dic={
}
for i in range(node_amount):
add,data,next_add=input().split()
list_dic[add]=[add,data,next_add]
lis=CreateList(list_dic,first_add)
lis=K_reverse(lis,K)
for i in range(len(lis)):
#范围是len(lis),而非node_amount,原因是并非所有的结点都在链表中
print("{0} {1} {2}".format(lis[i][0],lis[i][1],lis[i][2]))
以上程序对测试点5不通过,运行超时。
参考程序2(C语言)
#include <stdio.h>
#define LEN 100000
struct ListNode
{
int Address;
int Data;
int Next;
};
struct ListNode NodeSet[LEN],List[LEN];
int cnt=0;//cnt是链表中结点个数
void K_Reverse(int K)
{
struct ListNode temp;
int j,start,end;
start=0;
end=K-1;
while(end<=cnt-1)
{
int midlength=(end-start+1)/2;
for(j=0;j<=midlength-1;j++)
{
temp=List[j+start];
List[j+start]=List[end-j];
List[end-j]=temp;
}
start+=K;
end+=K;
}
}
int main()
{
int N,K,i,first,first_index;
scanf("%d%d%d",&first,&N,&K);
for(i=0;i<N;i++)
{
int temp_add,temp_data,temp_next;
scanf("%d%d%d",&temp_add,&temp_data,&temp_next);
NodeSet[temp_add].Address=temp_add;
NodeSet[temp_add].Data=temp_data;
NodeSet[temp_add].Next=temp_next;
}
while(first!=-1)
{
List[cnt].Address=NodeSet[first].Address;
List[cnt].Data=NodeSet[first].Data;
first=NodeSet[first].Next;
cnt++;
}
K_Reverse(K);
for(i=0;i<=cnt-2;i++)
{
List[i].Next=List[i+1].Address;
}
List[cnt-1].Next=-1;
for(i=0;i<cnt;i++)
{
if(List[i].Next==-1)
{
printf("%05d %d %d\n",List[i].Address,List[i].Data,List[i].Next);
}
else
{
printf("%05d %d %05d\n",List[i].Address,List[i].Data,List[i].Next);
}
}
return 0;
}
/*测试数据
00100 6 2
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
00100 6 2
00000 4 99999
00100 1 12309
68237 6 88888
33218 3 -1
99999 5 88888
12309 2 33218
*/
分析:
本题是PAT (Basic Level) Practice1025题,解决本题,分为两个步骤:
(1)根据给出的结点数据集,构造出链表的形态。
①在这之中有些结点可能根本不在链表上,因此链表的长度小于等于数据给出的结点个数,这一点需要注意
②在还原链表时,有两种思路,一种是最直接的方式,即利用两层循环,基于查找的方式,一个一个地将结点按顺序组织起来,这样的时间复杂度为O(N^2),即使参考程序1中Python中使用了字典结构,用了一个循环,但这样只是对逻辑抽象与问题处理的表达上,变得简单了,但本质上还是两层循环,这样对于大规模数据,时间性能较差;另一种方法(参考程序2)是模拟,即直接开100000的结构体数组空间,将结构体的下表索引模拟为题目所说的“地址”,而这与题目恰好是吻合的——结点“地址”占五位,在1-99999之间,结构体数组的空间刚好也够用,这样直接通过数组下标进行查找,大大提高了时间性能,时间复杂度为O(n),但空间复杂度就比较大了。参考程序2的解答也完全正确。
(2)组织好链表后,进行K-逆转。参考程序1直接使用了reversed内置函数。参考程序2很原始地用前后两两交换实现逆转。
可以看出,使用Python语言解题的代码量要比C语言少很多的,而且对于问题的表示、逻辑抽象时都很直接、方便。而且Python作为脚本语言,不像C语言那样要写一个个的函数、Java那样要写类、方法这样重视结构,在代码书写上比较灵活。
当然时间性能自然也要有所牺牲,Python的运行速度是C语言的10倍。所以大家在online judge上做题时,语言的选择上要做很好的权衡。
版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: