问题LeetCode链接
1.题目描述
反转一个单链表。
实例
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
2.分析
链表作为比较基础的数据结构，是一定要会的，以下将展示链表的逆序的两种方式。
3.解决
①迭代解决
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
"""
迭代
"""
if (not head) or head.val==None: # 避免链表为空的特殊情况
return head
current_node = head
pre_node = None # 定义前一个点
while current_node: # 判断条件为当前点是否为None
next_node = current_node.next
current_node.next = pre_node
pre_node = current_node # 将前一个点定义为当前点
head = pre_node # 可以直接return pre_node,这么写是比较好理解
current_node = next_node # 定义下一个循环的当前节点为下一个节点
return head
迭代的蛇皮走位写法，可能会有点晕
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
"""
迭代之蛇皮走位写法
"""
current_node,pre_node = head,None
while current_node:
# 主要是利用了python的一个特性，在交换值的时候（以下式子），左边的值是暂时不变的
pre_node,current_node.next,current_node = current_node,pre_node,current_node.next
return pre_node
②递归解决
递归这个很不好理解，可以参考这篇博客：
dashuai的博客-全面分析再动手的习惯：链表的反转问题（递归和非递归方式）
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
"""
递归的写法
递归重要的是你要学会倒着考虑问题
"""
if not head or head.next == None: # 递归终止条件（以及排除特殊值问题）
return head
else:
newhead = self.reverseList(head.next) # newhead一直是指向最后一个节点
head.next.next = head
head.next = None # 仅仅在第一个元素时候起作用(递归就是一个栈，后进先出，所以先考虑末尾，最后考虑头)
return newhead
