PAT class B exercise "reverse linked list" python solution

Original question

Given a constant K and a single chain table L, please write a program to reverse every k nodes in L. For example, if l is 1 → 2 → 3 → 4 → 5 → 6 and K is 3, then the output should be 3 → 2 → 1 → 6 → 5 → 4; if K is 4, then the output should be 4 → 3 → 2 → 1 → 5 → 6, that is, the last less than k elements are not reversed.

Input format

Each input contains 1 test case. The first line of each test case gives the address of the first node, the total number of nodes positive integer N (< 10510 ^ 5105), and the positive integer K (< N), that is, the number of sub chain nodes that need to be reversed. The address of the node is a 5-bit non negative integer, and the NULL address is represented by − 1.

Next there are N lines, each of which has the format:

Address Data Next

Where Address is the Address of the node, Data is the integer Data saved by the node, and Next is the Address of the Next node.

Output format

For each test case, the inverted chain list is output in sequence, with each node occupying a row, and the format is the same as the input.

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

my answer

There is a test timeout

Idea: define a dictionary. The elements in the dictionary are stored in the form of "Address": "Data Next". Then find the first meta node in the dictionary through the first address, and then find the direct successor of the first meta node in the dictionary by the Next of the first meta node. In the process of traversing along the chain, according to the required size of the inverted sub list n, each N node is a group, each node is stored in the form of tuples in the list linklist ABCD child, a list of N node tuples linklist ABCD child is put into a large list linklist, so on. For the last set of sub chains, the number of possible nodes is less than N, and it is not necessary to reverse for this set of sub chains.

When all nodes are stored in linklist in order and group, traverse linklist and take out a sub linked list (the sub linked list is of list type and contains node information of tuple type). If the number of nodes in the sub chain is equal to N, output node information from the back to the front; if the number of nodes in the sub chain is less than N, do not need to reverse, output directly as required Yes.

basicInfo = input().split()
dict_node = dict() # Define an empty dictionary with "node address" as the key and "node value and next node address" as the value
for i in range(int(basicInfo[1])):
    node = input()
    dict_node[node[:5]] = node[6:] # Save each node in the dictionary

linklist = [] # Define an empty list, where each element is also a list, and each element represents the child linked list to be reversed
linklist_child = [] # The list is used to store a sub linked list. The node information in the sub linked list is represented by a tuple in the list

pointer = basicInfo[0] # Define a "pointer" for forward looking
count = 0 # Counter, every time a complete sub linked list is found, count will return to zero
while pointer != '-1': # When the pointer does not reach the last node
    node_info = dict_node[pointer]
    node_info_list = node_info.split()
    node_info_list.insert(0, pointer)
    linklist_child.append(tuple(node_info_list))
    pointer = node_info_list[-1]
    count += 1
    
    if count == int(basicInfo[2]): # If the number of nodes in the sub linked list reaches the specified number, the counter returns to zero and the sub linked list is added to linklist
        count = 0
        linklist.append(linklist_child.copy()) # Note that you can't append (LinkList \ u child) directly here, because you need to execute linklist \ u child. Clear() on the next line
        linklist_child.clear()

# After the loop, judge whether there are remaining elements
if len(linklist_child) != 0:
    linklist.append(linklist_child)

flag = False # Indicates whether the first line is not printed
for linklistChild in linklist:
    if len(linklistChild) == int(basicInfo[2]): # Judge whether the number of nodes of the sub chain meets the requirements
        index = -1
        for i in linklistChild:
            node = linklistChild[index]
            if flag: # If the first line is not printed, the Address of the node (representing the Next value of the previous node) will be printed, and then the Address and Data values of the node will be printed
                print(node[0])
                print("{} {} ".format(node[0], node[1]), end='')
            else: # If the first line is printed, the Address and Data values of the node are output side by side
                print("{} {} ".format(node[0], node[1]), end='')
                flag = True
            index -= 1
    else:
        for node in linklistChild:
            if flag:
                print(node[0])
                print("{} {} ".format(node[0], node[1]), end='')
            else:
                print("{} {} ".format(node[0], node[1]), end='')
                flag = True
print("-1")
Published 42 original articles, won praise 27, visited 7462
Private letter follow

Tags: less

Posted on Sat, 14 Mar 2020 20:09:49 -0700 by Trader77