反转链表 (25)

[编程题]反转链表 (25)

热度指数：26480 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 146M，其他语言293M
算法知识视频讲解

给定一个常数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(<= 10⁵)、以及正整数K(<=N)，即要求反转的
子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。

接下来有N行，每行格式为：

Address Data Next

其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。

输出描述:

对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。

示例1

输入

00100 6 4<br/>00000 4 99999<br/>00100 1 12309<br/>68237 6 -1<br/>33218 3 00000<br/>99999 5 68237<br/>12309 2 33218

输出

00000 4 33218<br/>33218 3 12309<br/>12309 2 00100<br/>00100 1 99999<br/>99999 5 68237<br/>68237 6 -1

算法知识视频讲解

Python

棠荼

x=[0]*100000;y=[0]*100000;
st,n,k=map(int,input().split())
n2=0;
a=[];b=[];
for i in range(n):
    a.append(list(map(int,input().split())))
    x[a[i][0]]=a[i][2];
    y[a[i][0]]=a[i][1];
n=0
while st !=-1:
    b.append([st,y[st]]);
    st=x[st];
    n=n+1;
if(k<=n):
    b[:k]=b[k-1::-1]
    for i in range(k,n,k):
        if(i+k<=n):
            b[i:i+k]=b[i+k-1:i-1:-1]
for i in range(n-1):
    b[i].append(b[i+1][0])
b[-1].append(-1)
for i in b[:-1]:
    print("%05d %d %05d"%(i[0],i[1],i[2]))
print("%05d %d -1"%(b[-1][0],b[-1][1]))

发表于 2019-09-13 23:10:21 回复(0)

Python

cyd1310997

A, B, C = input().split()
B, C = eval(B), eval(C)
L = [input().split() for i in range(B)]
D = {i[0]:i for i in L}
p = A
L = [D[p]]
while D[p][2] != '-1':
    p = D[p][2]
    L.append(D[p])
L = [i[0] for i in L]
L = [L[i:i+C] for i in range(0, len(L), C)]
L = [reversed(i) if len(i) == C else i for i in L]
L = ' '.join([' '.join(i) for i in L]).split()
L = [D[i] for i in L]
for i, j in enumerate(L):
    j[2] = L[i + 1][0] if i != len(L) - 1 else '-1'
for i in L:
    print(' '.join(i))

编辑于 2019-08-25 17:49:27 回复(0)

Python

北风扬尘尘飞扬

通过的代码如下：

# -*- coding: utf-8 -*-

def method():
    st, n, k = map(int, input().split())
    lst=[None for i in range(100001)]
    out=[]
    for i in range(n):
        t = list(map(int, input().split()))
        lst[t[0]] = [t[1], t[2]]
    while st != -1:
        out.append([st, lst[st][0]])
        st = lst[st][1]
    time = len(out) // k
    for i in range(time):
        te = out[i * k:i * k + k]
        te.reverse()
        out[i * k:i * k + k] = te
    for i in range(len(out) - 1):
        print("%05d" % out[i][0] + " " + str(out[i][1]) + " " + "%05d" % out[i + 1][0])
    print("%05d" % out[len(out) - 1][0] + " " + str(out[len(out) - 1][1]) + " " + "-1")

if __name__ == '__main__':
    method()

部分通过的代码如下:(思路没错~)

# -*- coding : utf-8 -*-
import sys


def method():
    start_address, n, k = input().split()
    value_dict = {}
    for line in sys.stdin:
        address, data, next_i = line.split()
        value_dict[address] = (data, next_i)
    linklist = []
    next_i = start_address
    while next_i != '-1':
        address = next_i
        x = value_dict.get(next_i, None)
        if x is None:
            break
        data, next_i = x
        linklist.append((address, data, next_i))
    length = len(linklist)
    k = int(k)
    while length > 0:
        if length >= k:
            for i in range(k):
                address, data, next_i = linklist[k - 1 - i]
                print(address + ' ' + data + ' ' + next_i)
            length -= k
            del linklist[0:k]
        else:
            for i in range(length):
                address, data, next_i = linklist[i]
                print(address + ' ' + data + ' ' + next_i)
            length = 0
 if __name__ == '__main__':
    method()

发表于 2019-05-27 19:25:59 回复(0)

Python

qswhy

out,lst = [],[None for i in range(100001)]
st,num,k = map(int,input().split())
for i in range(num):
    t = list(map(int,input().split()))
    lst[t[0]] = [t[1],t[2]]
while st!=-1:
    out.append([st,lst[st][0]])
    st = lst[st][1]
time = len(out)//k
for i in range(time):
    te = out[i*k:i*k+k]
    te.reverse()
    out[i*k:i*k+k] = te
for i in range(len(out)-1):
    print("%05d"%out[i][0]+" "+str(out[i][1])+" "+"%05d"%out[i+1][0])
print("%05d"%out[len(out)-1][0]+" "+str(out[len(out)-1][1])+" "+"-1")

发表于 2019-03-26 10:12:23 回复(0)

Python