leetcode206-Reverse Linked List反转链表（python）_linked list的反转 python

法1：设置pre, current, next三个指针。时间消耗O(n),空间O(1)   （重点掌握法1即可）

# 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 head==None or head.next==None:
               return head
        pre=None
        cur=head
        next=None   # tmp临时变量
        while cur!=None:
            next=cur.next
            #交换
            cur.next=pre
            #更新
            pre=cur
            cur=tmp
        return pre

法2： 设置个辅助数组，将链表值存入数组中，反序数组后转化为链表。时间O(n),空间O(n)

# 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:
        arr=[]
        while head:
            arr.append(head.val)
            head=head.next
        newhead=ListNode(0)
        tmp=newhead
        for item in arr[::-1]:
            tmp.next=ListNode(item)
            tmp=tmp.next
        return newhead.next

 法3：和法1类似，区别是以链表的第二个元素作为循环变量。时间O(n)，空间O(1)

# 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 head==None or head.next==None:
            return head
        p1=head
        p2=head.next
        tmp=None
        while p2:
            tmp=p2.next
            p2.next=p1
            p1=p2
            p2=tmp
        head.next=None   #否则时间超出限制
        return p1

法4：递归法。时间O(n)，空间O(1)

# 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 head is None or head.next is None:
            return head
        else:
            newhead=self.reverseList(head.next)
            head.next.next=head
            head.next=None
        return newhead
 

参考：

用python介绍4种常用的单链表翻转的方法