Python LeetCode-206.反转链表（难度-简单）

问题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