206. 反转链表

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

解法一：迭代

加一个辅助头结点以记录插入位置，用头插法

# 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 not head or not head.next:
            return head
        Head = ListNode(0)    #辅助头结点
        Head.next = head
        p = head.next   #从第1个节点开始
        head.next = None    #第0个节点封尾，避免环链
        while p:
            tmp = p
            p = p.next
            tmp.next = Head.next    #头插法
            Head.next = tmp
        return Head.next

解法二：递归（较难）

方法非常巧妙，不需要借助辅助递归函数，直接递归。

initial:
1 -> 2 -> 3 -> 4 -> 5

after reverseList(2):
1 -> 2 <- 3 <- 4 <- 5
     |
    null
	
after operate on 1:
null <- 1 <- 2 <- 3 <- 4 <- 5

首先递归到最后一个非空节点，然后自底向上构造链表，每次对当前递归函数的head操作，将head与head.next之间的链反转。

# 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 not head or not head.next:    #边界
            return head
        newHead = self.reverseList(head.next)
        head.next.next = head    #反转链
        head.next = None    #原链置空，防止环链
        return newHead