Python - 反转链接列表类模块作为输入

Question

我正在处理接受链接列表作为输入的问题，在这一点上我甚至不知道如何设置示例链接列表。

我最初的问题是理解下面的指令：

Write a function that accepts a linked list as input, then reverses that linked list.

这是否仅仅涉及定义为扭转总结'作为一部分的以下或有Python中总结一个链表的一些其他的方式：

class Node(object): 

    # Initialize with a single datum and pointer set to None 

    def __init__(self, data=None, next_node=None): 
     self.data = data 
     self.next_node = next_node 

    # Returns the stored data 

    def get_data(self): 
     return self.data 

    # Returns the next node 

    def get_next(self): 
     return self.next_node 

    # Reset the pointer to a new node 

    def set_next(self, new_next): 
     self.next_node = new_next 

    def set_data(self, data): 
     self.data = data 

class LinkedList(object): 

    # Top node in the list created on __init__ 

    def __init__(self, head=None): 
     self.head = head 

    # Take in the new node and point the new node to the prior head O(1) 

    def insert(self, data): 
     new_node = Node(data) 
     new_node.set_next(self.head) 
     self.head = new_node 

    # Counts nodes O(n) 

    def size(self): 
     current = self.head 
     count = 0 
     while current: 
      count += 1 
      current = current.get_next() 
     return count 

    # Checks each node for requested data O(n) 

    def search(self, data): 
     current = self.head 
     found = False 
     while current and found is False: 
      if current.get_data() == data: 
       found = True 
      else: 
       current = current.get_next() 
     if current is None: 
      raise ValueError("Data not in list") 
     return current 

    # Similar to search, leapfrogs to delete, resetting previous node pointer to point to the next node in line O(n) 

    def delete(self, data): 
     current = self.head 
     previous = None 
     found = False 
     while current and found is False: 
      if current.get_data() == data: 
       found = True 
      else: 
       previous = current 
       current = current.get_next() 
     if current is None: 
      raise ValueError("Data not in list") 
     if previous is None: 
      self.head = current.get_next() 
     else: 
      previous.set_next(current.get_next()) 

Answer 1

看来你所有的基础链接列表类的代码都在那里。你只需要扭转你的链接列表。反转链表如下所示。

[1] - > [2] - > [3] - > NULL

你可以告诉大家1是头和3尾（这意味着它是在链表的最后一个节点因为它指向Python中的NULL或None）。你需要做的是找出一些算法，将采取该链接列表并产生这个结果。

[3] - > [2] - > [1] - > NULL

现在3是头，1是尾。

因此，使用伪代码：

Initalize 3 Nodes: prev, next, and current 
current = head 
prev = None 
next = None 
While current != None 
    next = current.next 
    current.next = prev 
    prev = current 
    current = next 
head = prev