0206._reverse_linked_list.md

206. Reverse Linked List

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/reverse-linked-list/description/

内容描述

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

用三个指针，分别指向prev，cur 和 nxt，然后loop一圈还算比较简单.

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev = None 
        cur = head
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        return prev

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

其实不用cur也可以

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
        prev = None
        while head.next:
            nxt = head.next
            head.next = prev
            prev = head
            head = nxt
        head.next = prev  
        return head

递归版本，可以再消化一下.

思路 3 - 时间复杂度: O(N)- 空间复杂度: O(1)******

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        def helper(head, new_head):
            if head:
                nxt = head.next
                head.next = new_head
                return helper(nxt, head)
            else:
                return new_head
                
        return helper(head, None)