如何在python中将链表的最后一个元素移动到第一个(代码下方)?

Question

#DSA-Prac-1
class Node:
def __init__(self,data):
self.__data=data
self.__next=None
def get_data(self):
return self.__data
def set_data(self,data):
self.__data=data
def get_next(self):
return self.__next
def set_next(self,next_node):
self.__next=next_node

class LinkedList:    
def __init__(self):
self.__head=None
self.__tail=None
def get_head(self):
return self.__head
def get_tail(self):
return self.__tail

def add(self,data):
new_node=Node(data)
if(self.__head is None):
self.__head=self.__tail=new_node
else:
self.__tail.set_next(new_node) 
self.__tail=new_node
def insert(self,data,data_before):
new_node=Node(data)
if(data_before==None):
new_node.set_next(self.__head)
self.__head=new_node
if(new_node.get_next()==None):
self.__tail=new_node
else:
node_before=self.find_node(data_before)
if(node_before is not None):
new_node.set_next(node_before.get_next()) 
node_before.set_next(new_node)   
if(new_node.get_next() is None):       
self.__tail=new_node
else:
print(data_before,"is not present in the Linked list")
def display(self):
temp=self.__head
while(temp is not None):
print(temp.get_data())
temp=temp.get_next()     

def find_node(self,data):
temp=self.__head
while(temp is not None):
if(temp.get_data()==data):
return temp
temp=temp.get_next()    
return None
def delete(self,data):
node=self.find_node(data)
if(node is not None):
if(node==self.__head):
if(self.__head==self.__tail):
self.__tail=None
self.__head=node.get_next()
else:
temp=self.__head
while(temp is not None):
if(temp.get_next()==node): 
temp.set_next(node.get_next())    
if(node==self.__tail):
self.__tail=temp
node.set_next(None)
break
temp=temp.get_next()    
else:
print(data,"is not present in Linked list")

def change_order(input_list):
'I need the code to be written here'
return input_list

input_list=LinkedList()
input_list.add(9)
input_list.add(3)
input_list.add(56)
input_list.add(6)
input_list.add(2)
input_list.add(7)
input_list.add(4)
result=change_order(input_list)
result.display()

只有函数change_order必须编写。不应在程序的其他部分进行任何更改。输入链表为 9->3->56->6->2->7->4，输出应为 4->9->3->56->6->2->7。
这就是我尝试过的。由于 linkedlist 类的头是一个私有属性，我在分配新头时遇到困难。

def change_order(input_list):
temp=input_list.get_head()
while temp and temp.get_next():
sec_last = temp
temp=temp.get_next()     
sec_last.set_next(None)
temp.set_next(input_list.get_head())

Answer 1

您的 LinkedList 类应该已经提供了完成此操作所需的所有功能，而无需自己弄乱指针：

data = input_list.get_tail().get_data()  # get last element
input_list.delete(data)                  # remove last element
input_list.insert(data, None)            # insert that element first

请注意，列表接口假定列表中的所有项都是唯一的;如果您有重复项，其中一些方法将无法正常工作，并且只会对第一个匹配项进行操作。 例如，如果在删除之前执行插入操作，则删除操作将删除刚插入的头部的项目，而不是要删除的尾部的项目。

这本质上是此列表实现的错误/约束;通常列表接口会为您提供某种迭代器，以允许您处理具有多个匹配项的情况。

如果您必须在赋值的参数下解决此问题，那么能够修改head并不是困难的部分(因为您可以通过insert可靠地做到这一点(，而是弹出tail(因为唯一允许您执行此操作的接口是delete，这将完全不允许通过引用访问节点， 因此，如果您尝试在有重复项时使用它来删除尾巴，则总是会做错误的事情(。 最简单的解决方案IMO是将整个列表转换为更好的格式，做任何您需要的事情，然后将其转换回来。 (如果目标是学习链表的工作原理，这是一个可怕的教训，但如果目标是了解有时你需要做一些愚蠢的事情来解决别人的无能，这是一个很好的教训。

def change_order(input_list):
'I need the code to be written here'
# Define helper functions to convert LinkedList to and from List.
def convert_linked_list_to_list(linked_list):
"""Converts a LinkedList to a native List."""
arr = []
node = input_list.get_head()
while node is not None:
arr.append(node.get_data())
node = node.get_next()     
return arr   
def rebuild_linked_list_from_list(linked_list, arr):
"""Replaces input LinkedList contents with native List contents."""
while linked_list.get_head() is not None:
linked_list.delete(linked_list.get_head().get_data())
for data in arr:
linked_list.add(data)
# Now do the order change using a List.
arr = convert_linked_list_to_list(input_list)
rebuild_linked_list_from_list(input_list, arr[-1:] + arr[:-1])
return input_list

在现实生活中，您将在此函数之外定义这些帮助程序，因为它们在其他情况下必然有用，在这些情况下，您需要以糟糕的接口不支持的方式操作这些LinkedList容器之一，但是赋值的参数要求包含所有内容change_order，所以你有它。