小白学算法-数据结构和算法教程: 反转链表

＃Python程序用于反转链表
＃时间复杂度：O（n）
＃空间复杂度：O（1）

#节点类
class Node:
	# 初始化节点对象的构造函数
	def __init__(self, data):
		self.data = data
		self.next = None


class LinkedList:

	＃初始化头部的函数
	def __init__(self):
		self.head = None

	# 反转链接列表的函数
	def reverse(self):
		prev = None
		current = self.head
		while(current is not None):
			next = current.next
			current.next = prev
			prev = current
			current = next
		self.head = prev

	# 在开头插入新节点的函数
	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	# 打印 LinkedList 的实用程序
	def printList(self):
		temp = self.head
		while(temp):
			print(temp.data, end=" ")
			temp = temp.next


# Driver code
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(85)

print ("Given linked list")
llist.printList()
llist.reverse()
print ("\nReversed linked list")
llist.printList()

给定链表
85 15 4 20 
反向链表
20 4 15 85

"""使用递归方法反转链接表的 Python3 程序
使用递归方法"""

# 链接列表节点

class Node:
	def __init__(self, data):
		self.data = data
		self.next = None

# 创建和处理列表操作

class LinkedList:
	def __init__(self):
		self.head = None # 列表的头部

	# 反转列表的方法
	def reverse(self, head):

		# 如果头部为空或已到达列表末尾
		if head is None or head.next is None:
			return head

		# 倒转其余列表
		rest = self.reverse(head.next)

		# 将第一个元素放在最后
		head.next.next = head
		head.next = None

		# 修复头部指针
		return rest

	# 返回显示格式的链接列表
	def __str__(self):
		linkedListStr = ""
		temp = self.head
		while temp:
			linkedListStr = (linkedListStr +
							str(temp.data) + " ")
			temp = temp.next
		return linkedListStr

	# 将新数据推送到列表头部
	def push(self, data):
		temp = Node(data)
		temp.next = self.head
		self.head = temp

linkedList = LinkedList()
linkedList.push(20)
linkedList.push(4)
linkedList.push(15)
linkedList.push(85)

print("Given linked list")
print(linkedList)

linkedList.head = linkedList.reverse(linkedList.head)

print("Reversed linked list")
print(linkedList)

给定链表
85 15 4 20
反向链表
20 4 15 85

＃简单的尾递归Python程序，用于反转链表

＃节点类
class Node:

	# 用于初始化节点对象的构造函数
	def __init__(self, data):
		self.data = data
		self.next = None


class LinkedList:

	# 初始化头部的函数
	def __init__(self):
		self.head = None

	def reverseUtil(self, curr, prev):

		# 如果是最后一个节点，将其标记为头
		if curr.next is None:
			self.head = curr

			# 更新前一个节点的下一个节点
			curr.next = prev
			return

		# 保存 curr.next 节点以供递归调用
		next = curr.next

		# 并更新下一步
		curr.next = prev

		self.reverseUtil(next, curr)

# 该函数主要调用 reverseUtil()
# 将 previous 设为 None

	def reverse(self):
		if self.head is None:
			return
		self.reverseUtil(self.head, None)

	# 在开头插入新节点的函数

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	# 打印链接的 LinkedList 的实用程序
	def printList(self):
		temp = self.head
		while(temp):
			print (temp.data, end=" ")
			temp = temp.next


# Driver code
llist = LinkedList()
llist.push(8)
llist.push(7)
llist.push(6)
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)

print ("Given linked list")
llist.printList()

llist.reverse()

print ("\nReversed linked list")
llist.printList()

给定链表
1 2 3 4 5 6 7 8 
反向链表
8 7 6 5 4 3 2 1

# 上述方法的 Python 代码

# 单链表的定义。
class ListNode:
	def __init__(self, val=0, next=None):
		self.val = val
		self.next = next


class Solution:

	# 反转链接列表的程序使用堆栈
	def reverseLLUsingStack(self, head):

		# 初始化变量
		stack, temp = [], head

		while temp:
			stack.append(temp)
			temp = temp.next

		head = temp = stack.pop()

		# 直到堆栈不空
		while len(stack) > 0:
			temp.next = stack.pop()
			temp = temp.next

		temp.next = None
		return head


if __name__ == "__main__":
	head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
	print("Given linked list")
	temp = head
	while temp:
		print(temp.val, end=' ')
		temp = temp.next
	obj = Solution()
	print("\nReversed linked list")
	head = obj.reverseLLUsingStack(head)
	while head:
		print(head.val, end=' ')
		head = head.next

给定链表
1 2 3 4 
反向链表
4 3 2 1