题目如下:
给定一个常数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个元素不反转。
输入格式:
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 105)、以及正整数K(<=N),即要求反转的子链结点的个数。结点的地址是5位非负整数,NULL地址用-1表示。
接下来有N行,每行格式为:
Address Data Next
其中Address是结点地址,Data是该结点保存的整数数据,Next是下一结点的地址。
输出格式:
对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。
输入样例:00100 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218输出样例:
00000 4 33218 33218 3 12309 12309 2 00100 00100 1 99999 99999 5 68237 68237 6 -1
题目解析:
此题做的比较晚,主要是因为当时不太熟悉链表那一套理论。现在来看,其实也不必按照链表的基本法,不过对链表有过了解后对题目会更友好一些。
关于python实现链表等数据结构可以慢慢等鄙人博客的更新,我会做一些微小的工作,在学习数据结构的同时将实现的代码记录下来,互相交流。excited!
这一题本人用了两种方法实现,但都是22分,测试点5运行超时。方法一参考了另一博客的思路,用列表实现反转,但那位兄弟测试点5是返回非0也不能过,所以鄙人认为不是python慢,仍然是有Bug,有一处陷入死循环之类的;方法二是利用的链表那一套理论的方法,比较麻烦,但是也很有意义。但是测试点5都过不去应该是代码的问题,或者题目哪里有陷阱考虑不到。有时间参考其他语言的方法看看。
先看方法一,关键就是列表反转那一句list[::-1]。代码如下:
add_head, length, k = input().split() length = int(length) k = int(k) lk = dict() for i in range(length): add, data, next = input().split() lk[add] = [int(data),next] linklst = [] addr = add_head while 1: # 将链表按顺序存入列表中,注意只存了本地址和数据 data = lk[addr][0] linklst.append([addr,data]) addr = lk[addr][1] if addr == '-1': break len_real = len(linklst) # 获得链表的真正长度 for i in range(len_real//k): # 分段反转 len_real 段 linklst[i*k:(i+1)*k] = linklst[i*k:(i+1)*k][::-1] linklst.append([-1,0]) # 列表末尾加-1,输出用的到 for i in range(len_real): lst = linklst[i] addr = lst[0] data = lst[1] print(addr,data,linklst[i+1][0])
这是参考那位博主的,因为认为是py慢打算优化一下,又改良了一番(仍然算方法一),将存储和反转同时进行,谁知还是过不去= =,贴出来也看一下~,如果速度没有提示,那么就很失败了,因为多了很多判断的语句,容易出错。
add_head, length, k = input().split() length = int(length) k = int(k) lk = dict() for i in range(length): add, data, next = input().split() lk[add] = [int(data),next] addr = add_head ret = [] while 1: # 将存储数据和反转一并进行 n = 0 linklst = [] while n!=k: data = lk[addr][0] linklst.append([addr,data]) addr = lk[addr][1] n += 1 if addr == '-1': break if n==k: # 通过判断n=k 将该段链表反转存入ret tmp = linklst[::-1] for item in tmp: ret.append(item) if addr == '-1' and n != k: # 当addr 为‘-1’时,可能结尾不足k,原样存入ret tmp = linklst[:] for item in tmp: ret.append(item) break elif addr == '-1' and n == k: # 若到结尾,恰好足够k,由于已经存入ret,直接break break len_real = len(ret) # 获得链表的真正长度 ret.append([-1,0]) # 列表末尾加-1,输出用的到 for i in range(len_real): lst = ret[i] addr = lst[0] data = lst[1] print(addr,data,ret[i+1][0])
方法二,是借鉴链表反转的理论(非递归方法),关于py的链表理论,可以自行查找相关资料,本人后续也会更新。由于这一问题不是真正的链表,这样做有点大材小用~有详细的注释,看不懂的话不妨去学习链表的知识。。
add_head, length, k = input().split() length = int(length) k = int(k) lk = dict() for i in range(length): add, data, next = input().split() lk[add] = [int(data),next] # print(lk) def rever(head_f, head_b): # 一段链表的反转函数 pre = head_b cur = head_f h = head_f while 1: head = cur tmp = lk[cur][1] lk[cur][1] = pre pre = cur cur = tmp if tmp == head_b: break return head # 返回这一段的链表头 def lengthreal(head): # 获得链表的真正长度 add = head n = 0 while add != '-1': add = lk[add][1] n += 1 return n length_real = lengthreal(add_head) head_f = add_head head_b = add_head for i in range(length_real//k): for j in range(k): head_b = lk[head_b][1] # head_b 移动至尾部,也是下一段的头部 head_new = rever(head_f,head_b) # 反转,得到该段链表头部 if i != 0: lk[head_f_last ][1] = head_new # 与上一段链表对接 else: head_fin = head_new # 最终链表的头部 是当i=0时的头部 head_f_last = head_f # 保留这一位置(该段尾部),与下一段链表对接 head_f = head_b # 移动head_f 到下一段的头部 # print(head_fin) # 新的链表头,便于输出 add = head_fin while 1: add_next = lk[add][1] print(add,lk[add][0],add_next) add = add_next if add == '-1': break写了这么多方法,都是22分,很尴尬,还请大佬指教,看着22分很别扭。。