206_反转链表

类型：链表

• 206. 反转链表 💚

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

  ❓ 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

  💡 迭代

  在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

  class Solution:
      def reverseList(self, head: ListNode) -> ListNode:
          if not head:
              return None
          leftNode = head
          rightNode = head.next
          leftNode.next = None
          while rightNode:
              tempNode = rightNode.next
              rightNode.next = leftNode
              leftNode = rightNode
              rightNode = tempNode
          return leftNode

  时间复杂度：O(n)，空间复杂度：O(1)

  💡 递归

  class Solution:
      def rec(self, node):
          if node.next:
              tailNode = self.rec(node.next)
              node.next = None
              tailNode.next = node
              return node
          else:
              return node
  
      def reverseList(self, head: ListNode) -> ListNode:
          if not head:
              return None
          tail = head
          while tail.next:
              tail = tail.next
          self.rec(head)
          return tail

  时间复杂度：O(n)，空间复杂度：O(n)