给定一个指向链表头节点的指针,任务是反转链表。我们需要通过更改节点之间的链接来反转列表。
例子:
输入:以下链表的头 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来跟踪节点以更新反向链接。
请按照以下步骤解决问题:
下面是上述方法的实现:
#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
时间复杂度: O(N),遍历大小为N的链表。 辅助空间: O(1)
这个想法是使用递归到达链表的最后一个节点,然后开始反转链表。
请按照以下步骤解决问题:
下面是上述方法的实现:
"""使用递归方法反转链接表的 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
时间复杂度: O(N),每个节点访问一次辅助空间: O(N),函数调用栈空间
这个想法是维护三个指针previous、current和next,递归访问每个节点并使用这三个指针建立链接。
请按照以下步骤解决问题:
下面是上述方法的实现:
#简单的尾递归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
时间复杂度: O(N),访问大小为 N 的链表的每个节点。 辅助空间: O(N),函数调用栈空间
这个想法是将所有节点存储在堆栈中,然后创建一个反向链表。
请按照以下步骤解决问题:
下面是上述方法的实现:
# 上述方法的 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
时间复杂度: O(N),访问大小为N的链表的每个节点。 辅助空间: O(N),空间用于存储堆栈中的节点。