(python3)1025. 反转链表 (22分)

时间:2021-01-18 19:14:15

题目如下:

给定一个常数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分很别扭。。