Python 反转链表
Python Reverse a Linked List
我正在做一个Python程序，实现链表以支持一些功能，我需要做的功能之一是反转堆栈。我制作了一个节点、LinkedList 和 Stack 类，这是我目前的代码：
class ListNode:
def __init__(self, Object):
self.Object = Object
self.next = None
class LinkedList:
def __init__(self):
self.head = None # first node
self.tail = None # last node
def addLast(self, Object):
newNode = ListNode(Object)
if self.head == None:
self.head = newNode
self.tail = newNode
else:
self.tail.next = newNode
self.tail = newNode
def removeFirst(self):
if self.head == None:
return
self.head = self.head.next
if self.head == None:
self.tail = None
def removeLast(self, Object):
if self.head == None:
return
current = self.head
prev = None
while current.next != None:
prev = current
current = current.next
if prev == None:
self.head = None
self.tail = None
else:
prev.next = None
self.tail = prev
def get(self, index):
current = self.head
i = 0
while i < index and current != None:
current = current.next
i = i + 1
if current != None and index >= 0:
return current.Object
else:
return None
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.next
return count
def isEmpty(self):
return self.head == None
def printList(self):
if self.head != None:
current = self.head
while current != None:
print(current.Object, end = ' ')
current = current.next
print()
# -------------------- STACK ---------------------------------------------------
class Stack:
# constructor implementation
def __init__(self):
self.llist = LinkedList()
def front(self):
return self.llist.get(0)
def dequeue(self):
self.llist.removeFirst()
def queue(self, Object):
self.llist(Object)
def push(self, Object):
self.llist.addLast(Object)
def pop(self, Object):
self.llist.removeLast(Object)
def printStack(self):
self.llist.printList()
def size(self):
return self.llist.size()
def isEmpty(self):
return self.llist.isEmpty()
# ----------------------- Reverse LIST ------------------------------
def Reverse(S):
# S is a Stack Object
这是我对这个问题的尝试：
def rRecursive( self ) :
self._rRecursive( self.head )
def _reverseRecursive( self, n ) :
if None != n:
right = n.next
if self.head != n:
n.next = self.head
self.head = n
else:
n.next = None
self._rRecursive( right )
def Reverse(S):
s.rRecursive()
如果这是一个普通列表，我可以使用 [::-1] 轻松反转它，但我不能，因为链表是一个对象。我在想也许我可以使用临时值，这样我就可以将堆栈的开头附加到列表中，然后以某种方式将其转换回堆栈对象。
复制编辑：我的程序的目标是使用现有的 Stack 并将其反转。 linked post 处理的是已经是列表格式的链表。
def get(self, index):
current = self.head
i = 0
while i < index and current != None:
current = current.next
i = i + 1
if current != None and index >= 0:
return current.Object
else:
return None
编辑 2：添加了我的 get 函数。
class Stack:
# constructor implementation
def __init__(self):
self.llist = LinkedList()
def front(self):
return self.llist.get(0)
# push method implementation
def push(self, Object):
self.llist.addLast(Object)
def pop1(self):
self.llist.removeLast1()
def Reverse(S):
new_stack = Stack()
while not S.isEmpty():
new_stack.push(S.front())
S.pop1()
return new_stack
# Current Stack after Push: 12 14 40 13
# Stack after Pop: 12 14 40
# Stack after Reversal: 12 12 12
编辑 3：添加了我的代码返工，它 returns 一遍又一遍地返回第一个元素的错误反转。
您不必 fiddle 在反转函数中使用 link 指针。我假设您的堆栈有一个 pop() 方法和其他基础知识；如果没有，则将您的 removeFirst 函数克隆到 return 已删除的节点。
现在，递归函数很简单：弹出列表的头部，反转剩余堆栈（如果有），并将弹出的节点添加到末尾。这能解决您的问题吗？
def reverseStack(self):
move_me = self.pop()
if not self.isEmpty():
return (self.reverseStack()).addLast(move_me)
else:
new_stack = Stack()
return new_stack.addLast(move_me)
使用基本的堆栈操作反转堆栈非常容易。从旧堆栈中弹出每个项目并将其推入新堆栈。
def reverse(stack):
new_stack = Stack()
while not stack.isEmpty():
new_stack.push(stack.front())
stack.pop()
return new_stack
你可以做一些类似的事情来破坏性地反转 Stack 中的 LinkedList 同时重用堆栈对象本身，你只需要使用列表操作而不是堆栈操作为他们取了别名。
说到堆栈操作，您可能会发现如果从前端而不是后端压入和弹出，您的堆栈性能会更好。从链表末尾删除一个项目需要遍历整个列表（以找到倒数第二个节点）。相比之下，无论是从前面添加还是从前面删除都很快。
使用基本数据结构反转事物的常用算法是利用堆栈是先进后出数据结构这一事实。这意味着如果您 pop 直到堆栈为空，您将以与 push 编辑它们相反的顺序获得项目。
但看起来您想通过递归函数而不是显式堆栈来执行此操作 - 在这种情况下，您的函数通常会获取前面的元素，然后 递归数据结构的其余部分，然后 处理第一个元素。这将按顺序关闭所有元素，但在每次递归调用完成时以相反的顺序处理它们，然后您将返回调用堆栈。如果您需要将元素添加到反向数据结构中（而不仅仅是打印它们），您可以通过 return 值构建它，注意一旦当前元素之后的所有内容都具有反向，您只需要将那个元素附加到前面，你就会得到你收到的所有东西的反面。
解决此问题的其他方法：作弊。
定义一个 __iter__ 方法（这在任何情况下都有意义；迭代是核心 Python 行为）以使您的类型可迭代。简单示例：
def __iter__(self):
cur = self.head
while cur is not None:
yield cur.Object
cur = cur.next
然后就这样做：
values = list(self) # Creates a list containing the current set of values
self.head = self.tail = None # Clear existing linked list
# Add back all the values in reverse order
for value in reversed(values):
self.addLast(value)
当然，与正确执行相比，它在内存 allocation/deallocation 开销方面的效率可能较低。但效果可能微乎其微，它极大地简化了实现代码。
当然，正确地做起来并不难，只是稍微有点混乱（完全未经测试，但应该接近正确）：
def reverse(self):
# Start at beginning, which will be new end
cur, last = self.head, None
# Reverse head and tail pointers in advance
self.head, self.tail = self.tail, self.head
# Traverse while reversing direction of each node pointer
while cur is not None:
# Tuple pack and unpack allows one-line variable swap
cur.next, cur, last = last, cur.next, cur
class Node(object):
def __init__(self, data=None, next_node=None):
self.data = data
self.next = next_node
def Reverse(head):
if head == None :
return None
elif head.next == None :
return head # returns last element from stack
else :
temp = head.next # stores next element while moving forward
head.next = None # removes the forward link
li = Reverse(temp) # returns the last element
temp.next = head # now do the reverse link here
return li
def main() :
temp4 = Node(4,None)
temp3 = Node(3,temp4)
temp2 = Node(2,temp3)
head = Node(1,temp2)
res = Reverse(head)
while res != None :
print(res.data)
res = res.next
main()
我正在做一个Python程序，实现链表以支持一些功能，我需要做的功能之一是反转堆栈。我制作了一个节点、LinkedList 和 Stack 类，这是我目前的代码：
class ListNode:
def __init__(self, Object):
self.Object = Object
self.next = None
class LinkedList:
def __init__(self):
self.head = None # first node
self.tail = None # last node
def addLast(self, Object):
newNode = ListNode(Object)
if self.head == None:
self.head = newNode
self.tail = newNode
else:
self.tail.next = newNode
self.tail = newNode
def removeFirst(self):
if self.head == None:
return
self.head = self.head.next
if self.head == None:
self.tail = None
def removeLast(self, Object):
if self.head == None:
return
current = self.head
prev = None
while current.next != None:
prev = current
current = current.next
if prev == None:
self.head = None
self.tail = None
else:
prev.next = None
self.tail = prev
def get(self, index):
current = self.head
i = 0
while i < index and current != None:
current = current.next
i = i + 1
if current != None and index >= 0:
return current.Object
else:
return None
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.next
return count
def isEmpty(self):
return self.head == None
def printList(self):
if self.head != None:
current = self.head
while current != None:
print(current.Object, end = ' ')
current = current.next
print()
# -------------------- STACK ---------------------------------------------------
class Stack:
# constructor implementation
def __init__(self):
self.llist = LinkedList()
def front(self):
return self.llist.get(0)
def dequeue(self):
self.llist.removeFirst()
def queue(self, Object):
self.llist(Object)
def push(self, Object):
self.llist.addLast(Object)
def pop(self, Object):
self.llist.removeLast(Object)
def printStack(self):
self.llist.printList()
def size(self):
return self.llist.size()
def isEmpty(self):
return self.llist.isEmpty()
# ----------------------- Reverse LIST ------------------------------
def Reverse(S):
# S is a Stack Object
这是我对这个问题的尝试：
def rRecursive( self ) :
self._rRecursive( self.head )
def _reverseRecursive( self, n ) :
if None != n:
right = n.next
if self.head != n:
n.next = self.head
self.head = n
else:
n.next = None
self._rRecursive( right )
def Reverse(S):
s.rRecursive()
如果这是一个普通列表，我可以使用 [::-1] 轻松反转它，但我不能，因为链表是一个对象。我在想也许我可以使用临时值，这样我就可以将堆栈的开头附加到列表中，然后以某种方式将其转换回堆栈对象。
复制编辑：我的程序的目标是使用现有的 Stack 并将其反转。 linked post 处理的是已经是列表格式的链表。
def get(self, index):
current = self.head
i = 0
while i < index and current != None:
current = current.next
i = i + 1
if current != None and index >= 0:
return current.Object
else:
return None
编辑 2：添加了我的 get 函数。
class Stack:
# constructor implementation
def __init__(self):
self.llist = LinkedList()
def front(self):
return self.llist.get(0)
# push method implementation
def push(self, Object):
self.llist.addLast(Object)
def pop1(self):
self.llist.removeLast1()
def Reverse(S):
new_stack = Stack()
while not S.isEmpty():
new_stack.push(S.front())
S.pop1()
return new_stack
# Current Stack after Push: 12 14 40 13
# Stack after Pop: 12 14 40
# Stack after Reversal: 12 12 12
编辑 3：添加了我的代码返工，它 returns 一遍又一遍地返回第一个元素的错误反转。
您不必 fiddle 在反转函数中使用 link 指针。我假设您的堆栈有一个 pop() 方法和其他基础知识；如果没有，则将您的 removeFirst 函数克隆到 return 已删除的节点。
现在，递归函数很简单：弹出列表的头部，反转剩余堆栈（如果有），并将弹出的节点添加到末尾。这能解决您的问题吗？
def reverseStack(self):
move_me = self.pop()
if not self.isEmpty():
return (self.reverseStack()).addLast(move_me)
else:
new_stack = Stack()
return new_stack.addLast(move_me)
使用基本的堆栈操作反转堆栈非常容易。从旧堆栈中弹出每个项目并将其推入新堆栈。
def reverse(stack):
new_stack = Stack()
while not stack.isEmpty():
new_stack.push(stack.front())
stack.pop()
return new_stack
你可以做一些类似的事情来破坏性地反转 Stack 中的 LinkedList 同时重用堆栈对象本身，你只需要使用列表操作而不是堆栈操作为他们取了别名。
说到堆栈操作，您可能会发现如果从前端而不是后端压入和弹出，您的堆栈性能会更好。从链表末尾删除一个项目需要遍历整个列表（以找到倒数第二个节点）。相比之下，无论是从前面添加还是从前面删除都很快。
使用基本数据结构反转事物的常用算法是利用堆栈是先进后出数据结构这一事实。这意味着如果您 pop 直到堆栈为空，您将以与 push 编辑它们相反的顺序获得项目。
但看起来您想通过递归函数而不是显式堆栈来执行此操作 - 在这种情况下，您的函数通常会获取前面的元素，然后 递归数据结构的其余部分，然后 处理第一个元素。这将按顺序关闭所有元素，但在每次递归调用完成时以相反的顺序处理它们，然后您将返回调用堆栈。如果您需要将元素添加到反向数据结构中（而不仅仅是打印它们），您可以通过 return 值构建它，注意一旦当前元素之后的所有内容都具有反向，您只需要将那个元素附加到前面，你就会得到你收到的所有东西的反面。
解决此问题的其他方法：作弊。
定义一个 __iter__ 方法（这在任何情况下都有意义；迭代是核心 Python 行为）以使您的类型可迭代。简单示例：
def __iter__(self):
cur = self.head
while cur is not None:
yield cur.Object
cur = cur.next
然后就这样做：
values = list(self) # Creates a list containing the current set of values
self.head = self.tail = None # Clear existing linked list
# Add back all the values in reverse order
for value in reversed(values):
self.addLast(value)
当然，与正确执行相比，它在内存 allocation/deallocation 开销方面的效率可能较低。但效果可能微乎其微，它极大地简化了实现代码。
当然，正确地做起来并不难，只是稍微有点混乱（完全未经测试，但应该接近正确）：
def reverse(self):
# Start at beginning, which will be new end
cur, last = self.head, None
# Reverse head and tail pointers in advance
self.head, self.tail = self.tail, self.head
# Traverse while reversing direction of each node pointer
while cur is not None:
# Tuple pack and unpack allows one-line variable swap
cur.next, cur, last = last, cur.next, cur
class Node(object):
def __init__(self, data=None, next_node=None):
self.data = data
self.next = next_node
def Reverse(head):
if head == None :
return None
elif head.next == None :
return head # returns last element from stack
else :
temp = head.next # stores next element while moving forward
head.next = None # removes the forward link
li = Reverse(temp) # returns the last element
temp.next = head # now do the reverse link here
return li
def main() :
temp4 = Node(4,None)
temp3 = Node(3,temp4)
temp2 = Node(2,temp3)
head = Node(1,temp2)
res = Reverse(head)
while res != None :
print(res.data)
res = res.next
main()