反转链表链表的反转
给定一个指向链表头节点的指针，任务是反转链表。我们需要通过更改节点之间的链接来反转列表。
例子：
输入：以下链表的头 1->2->3->4->NULL 输出：链表应更改为 4->3->2->1->NULL 输入：以下链表的头 1->2->3->4->5->NULL 输出：链表应更改为 5->4->3->2->1->NULL 输入：NULL 输出：NULL 输入：1->NULL 输出：1->NULL
通过迭代法反转链表：
这个想法是使用三个指针curr、prev和next来跟踪节点以更新反向链接。
插图：
请按照以下步骤解决问题：
- 将三个指针prev初始化为 NULL，将 curr 初始化为head，将 next初始化为 NULL。
- 遍历链表。在循环中，执行以下操作：
- 在更改curr的下一个之前，存储下一个节点
- 下一个 = 当前 -> 下一个
- 现在将curr的next指针更新为prev
- 当前 -> 下一个 = 上一个
- 将prev更新为curr，将curr 更新为next
- 上一个 = 当前
- 当前 = 下一个
下面是上述方法的实现：
代码语言：javascript复制＃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()输出
代码语言：javascript复制给定链表
85 15 4 20
反向链表
20 4 15 85时间复杂度： O(N)，遍历大小为N的链表。 辅助空间： O(1)
使用递归反转链表：
这个想法是使用递归到达链表的最后一个节点，然后开始反转链表。
插图：
请按照以下步骤解决问题：
- 将链表分为两部分——第一个节点和链表的其余部分。
- 对链表的其余部分调用reverse。
- 将其余链表链接到第一个。
- 将头指针修复为 NULL
下面是上述方法的实现:
代码语言：javascript复制"""使用递归方法反转链接表的 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)输出
代码语言：javascript复制给定链表
85 15 4 20
反向链表
20 4 15 85时间复杂度： O(N)，每个节点访问一次辅助空间： O(N)，函数调用栈空间
通过尾递归方法反转链表：
这个想法是维护三个指针previous、current和next，递归访问每个节点并使用这三个指针建立链接。
请按照以下步骤解决问题：
- 首先用当前的下一个节点更新下一个，即next = current->next
- 现在建立从当前节点到前一个节点的反向链接，即 curr->next = prev
- 如果访问的节点是最后一个节点，则只需从当前节点到前一个节点进行反向链接并更新头。
下面是上述方法的实现：
代码语言：javascript复制＃简单的尾递归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()输出
代码语言：javascript复制给定链表
1 2 3 4 5 6 7 8
反向链表
8 7 6 5 4 3 2 1时间复杂度： O(N)，访问大小为 N 的链表的每个节点。 辅助空间： O(N)，函数调用栈空间
使用Stack反转链表：
这个想法是将所有节点存储在堆栈中，然后创建一个反向链表。
请按照以下步骤解决问题：
- 将节点（值和地址）存储在堆栈中，直到输入所有值。
- 一旦所有条目完成，将头指针更新到最后一个位置（即最后一个值）。
- 开始弹出节点（值和地址）并以相同的顺序存储它们，直到堆栈为空。
- 将堆栈中最后一个节点的下一个指针更新为 NULL。
下面是上述方法的实现：
代码语言：javascript复制# 上述方法的 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输出
代码语言：javascript复制给定链表
1 2 3 4
反向链表
4 3 2 1时间复杂度： O(N)，访问大小为N的链表的每个节点。 辅助空间： O(N)，空间用于存储堆栈中的节点。
