[数据结构与算法]206 反转链表

反转链表

反转链表

一、有关python基础知识

1、python3新增 – 箭头的作用

函数参数中的冒号是参数的类型建议符，告诉程序员希望传入的实参的类型（这个类型也可以自己定义的类）。
函数后面跟着的箭头是函数返回值的类型建议符，用来说明该函数返回的值是什么类型。

2、if not

Python 中的 if 语句检查一个特定的条件，如果条件为真，则执行一个代码块。
if not 的作用与 if 语句相反。它测试一个条件是否为假，然后执行一些语句。

3、指针的用法

# 声明指针 -- 进行赋值即可
# 指针pre
pre = None

二、思路

1、迭代法

图解反转链表

# Definition for singly-linked list.
# 节点的定义
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 定义两个指针
        pre = None
        cur = head
        
        # 遍历整个链表
        # 结束条件:cur指向空，返回：pre
        while (cur is not None):
            # 在进行反转之前存储cur.next
            temp = cur.next
            
            # 指针反转
            cur.next = pre
            
            # 由于是遍历操作，所以需要移动两个指针
            pre = cur
            cur = temp
            
        return pre
        

问题：
1、null和None的区别

• None是一个对象，而NULL是一个类型。
• Python中没有NULL，只有None，None有自己的特殊类型NoneType。
• None不等于0、任何空字符串、False等。

2、递归法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 定义一个两个节点的通用反转函数
        def reverse(pre,cur):
            if cur is None:
                return pre
            
            temp = cur.next
            
            cur.next = pre
            
            return reverse(cur,temp)
        
        return reverse(None,head)