• 分类：LinkedList
• 时间复杂度: O(n)
• 空间复杂度: 迭代:O(1),递归O(n)

206. Reverse Linked List

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL进阶:

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/reverse-linked-list

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码1：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def helper(self, res, head):
        if head == None:
            return res

        tmp = head.next
        head.next = res
        return self.helper(head,tmp)

    def reverseList(self, head: ListNode) -> ListNode:
        res = None
        if head == None:
            return res
        
        return self.helper(res,head)

代码2：

# 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:
        res = None
        if head == None:
            return res
        
        pointer = head
        while(pointer!=None):
            tmp = pointer.next
            pointer.next = res
            res = pointer
            pointer = tmp
        
        return res

讨论：

1.迭代和递归两种方法，b站上的大圣讲题讲的很清楚，而且比较简短，建议一听