Reverse linked list Python

leetCode The first 206 topic Reverse a linked list .
link ：https://leetcode-cn.com/problems/reverse-linked-list
Here's the head node of the list head , Please reverse the list , And return the inverted linked list .

Example 1：

Input ：head = [1,2,3,4,5]
Output ：[5,4,3,2,1]

Example 2:

Input ：head = [1,2]
Output ：[2,1]

Example 3：

 Input ：head = []
Output ：[]

Tips ：

 The number range of nodes in the linked list is [0, 5000]
-5000 <= Node.val <= 5000

Tips ：

 The number range of nodes in the linked list is [0, 5000]
-5000 <= Node.val <= 5000

Advanced ： The linked list can be inverted by iteration or recursion . Can you solve the problem in two ways ？

A simple question about force deduction , Just define three pointers , Separate the current pointer and the front and back nodes of the pointer . Keep moving these pointers , Then change the direction of the node .

## python3
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
while cur != None:
ne = cur.next
cur.next = pre
pre = cur
cur = ne
return pre

Of course , This problem must be a recursive problem , Because we reverse a linked list , Is to reverse a node with a shorter list that has been reversed

Define recursive functions , Returns the tail pointer of the inverted linked list
When head.next Pointing to space time , Go straight back to head
When head.next When the pointer is not empty , We need to head The tail pointer of the following linked list , That is, call itself , The parameter passed is head.next（ The scale of the problem becomes smaller ）
Of the resulting tail pointer next Part points to the current head
take head return , Then the current head Is the tail pointer of the inverted linked list

---

If you write in this way , What we finally get is the tail pointer of the inverted linked list , Lost the header pointer of the reverse linked list .
So you need a member variable , Keep the header pointer of the reverse linked list , That is, the tail pointer of the original linked list .

## python3
class Solution1:
tail = ListNode()
def reverseList(self, head: ListNode) -> ListNode:
if head == None:
return head
head = self.digui(head)
return self.tail
def digui(self, head: ListNode) -> ListNode:
if head.next == None:
self.tail = head
return head
else:
temp = self.digui(head.next)
temp.next = head
head.next = None
return head