【LeetCode 206】反转链表（Python）_手撕代码目leetcode 206、反转链表python

一、题目
反转一个单链表。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

二、重难点
重点在于理解单链表，是由两个单元组成的一个存放值的value和一个指向下一节点的指针next组成。
我第一想法还是使用递归调用，因为上两篇文章都用的是递归调用，很好理解。

三、代码
1.递归：通过调用reverseList得到（1（2（3（4（5）））））这样一个顺序，因为是先运算最里面的括号，所以要改变（5）next标签的指向从none改成head(none–>4)，然后改变它上一级（4）的标签为none, 就可以继续进行递归调用直到改变所有的指针标签使之变成倒序。

# 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 not head.next :return head
        new=self.reverseList(head.next)
        head.next.next=head
        head.next=None
        return new
1
2
3
4
5
6
7
8
9
10
11
12
13

2.迭代:迭代需要通过中间变量来进行传递，也就是利用指针来做。我觉得理解其来要更绕一点，更难，下面的代码是别人的，我并没有大看懂，太绕了。具体的解释可以看下面的链接，里面有动画演示过程，多看几遍应该能懂，只是对于我来说自己写还是有难度。
https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/

# 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:
        pre=None
        cur=head
        while cur:
            tmp=cur.next
            cur.next=pre
            pre=cur
            cur=tmp
        return pre
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

根据运行结果来看，迭代的方法从用时和内存消耗上来说都优于递归，所以最好掌握第二种写法。多看两遍背会也算。（写给自己的话）原因：迭代空间复杂度是O(1)，递归是O（n）。时间复杂度都是一样的O(n)。