反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解法一：头插法

增加哨兵节点，每次迭代先备份head.next，然后修改head.next，最后修改dummy.next。

  1. class Solution:
  2.     def reverseList(self, head: ListNode) -> ListNode:
  3.         dummy = ListNode(0)
  4.         while head:
  5.             nxt = head.next
  6.             head.next = dummy.next
  7.             dummy.next = head
  8.             head = nxt
  9.         return dummy.next

解法二：双指针法

使用pre和cur指向相邻的两个节点，将pre->cur改成pre<-cur，迭代至cur == None，此时pre指向原链表的最后一个节点，即新的表头。

  1. class Solution:
  2.     def reverseList(self, head: ListNode) -> ListNode:
  3.         pre, cur = None, head
  4.         while cur:
  5.             tmp = cur.next
  6.             cur.next = pre
  7.             pre, cur = cur, tmp
  8.         return pre

解法三：递归

子问题：head指向一个已经反转完成的链表尾部元素，将head与尾部元素进行反转
退出条件：链表为空或仅有一个元素

  1. class Solution:
  2.     def reverseList(self, head: ListNode) -> ListNode:
  3.         if not head or not head.next:
  4.             return head
  5.         new_head = self.reverseList(head.next)
  6.         head.next.next = head
  7.         head.next = None
  8.         return new_head