题目
给定一个单链表的头节点 head ，请实现反转链表，并返回反转后的链表。
例如：
原链表转换为列表：[1, 2, 3, 4, 5]
最终的链表转换为列表：[5, 4, 3, 2, 1]原链表转换为列表：[1, 2]
最终的链表转换为列表：[2, 1]原链表转换为列表：[]
最终的链表转换为列表：[]
已知 链表节点的定义、链表与列表相互转换 的代码如下：
class ListNode: # 单链表
def __init__(self, val=0, next=None):
self.val = val # 链表节点上存储的元素
self.next = next # 指向下一个链表节点
def list_to_list_node(numbers): # 将列表转换为单向链表，并返回链表的头节点
dummy_head = ListNode(0)
pre = dummy_head
for number in numbers:
pre.next = ListNode(number)
pre = pre.next
pre = dummy_head.next
return pre
def list_node_to_list(node): # 将单向链表转换为列表
result = []
while node:
result.append(node.val)
node = node.next
return result
实现思路
- 设置两个指针：cur、pre，分别指向当前节点和前一个节点，cur默认指向链表头节点head，pre默认为None
- 当 cur 非空时进行循环，我们要实现链表的反转，只需要在每次循环过程中让 cur 指向 pre ，这样操作下来就能让当前节点指向其前一个节点
- 循环结束后得到的就是反转后的链表，注意此时 pre 指向原链表中的最后一个节点，我们只需要把 pre 返回即可
代码实现--迭代
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur = head # 当前节点
pre = None # 前一个节点
while cur is not None:
tmp_node = cur.next # 临时保存当前节点的下一个节点 cur.next , 下一步要改变 cur.next
cur.next = pre # 反转, 当前节点通过 next 指向前一个节点
pre = cur # 将前一个节点变为当前节点
cur = tmp_node # 将当前节点变为保存的临时节点
return pre
上面代码中使用了一个中间变量 tmp_node ，其实我们可以直接利用Python的多元赋值来完成，从而使代码更加简洁。优化如下：
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur, pre = head, None # 当前节点，前一个节点
while cur is not None:
# 当前节点通过 next 指向前一个节点，将前一个节点变为当前节点，将当前节点变为下一个节点
cur.next, pre, cur = pre, cur, cur.next
return pre
代码实现--递归
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
return self.reverse_recursive(None, head)
def reverse_recursive(self, pre: ListNode, cur: ListNode) -> ListNode:
if cur is None:
return pre
tmp_node = cur.next # 临时保存当前节点的下一个节点 cur.next , 下一步要改变 cur.next
cur.next = pre # 反转，当前节点通过 next 指向前一个节点
return self.reverse_recursive(cur, tmp_node)
更多Python编程题，等你来挑战：Python编程题汇总（持续更新中……）
网友评论