leetcode 206. 反转链表(python)_手撕代码leetcode 206、反转链表python

题目链接

题目描述：

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解题思路：

解法一：头插法
将原链表的每一个元素按照头插法插入到一个空链表中，即可实现链表的反转，注意每次在执行头插法时，首先要将指向原链表next的元素单独保存，否则在头插法的过程中会丢失。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        node=ListNode(-1)
        while head:
            curr=head.next#保存head的next
            head.next=node.next
            node.next=head
            head=curr
        return node.next
1
2
3
4
5
6
7
8
9

解法二：
用数组存放链表节点
把链表的节点的存放在数组中，再将数组中的元素依次指向前一个元素，实现链表的反转，时间复杂度为o（2n）

class Solutio