dd定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例：

输入：1->2->3->4->5->NULL
输出：5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

解题思路：

如下图所示，题目要求将链表反转。本文介绍迭代(双指针)、递归两种实现方法。

方法一：迭代(双指针)

考虑遍历链表，并在访问各节点时修改next引用指向，算法流程见注释。

复杂度分析：

• 时间复杂度O(N):遍历链表使用线性大小时间。
• 空间复杂度O(N):变量pre和cur使用常数大小额外空间。

# Definition for singly-linked list.
# class ListNode:
# 	def __init__(self, x):
# 		self.val = x
# 		self.next = None
class Solution:
	def reverseList(self, head):
		cur, pre = head, None
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre

方法二：递归

考虑使用递归法遍历链表，当越过尾节点后终止递归，在回溯时修改各节点的next引用指向。

return(cur, pre)递归函数：

1. 终止条件：当cur为空，则返回尾节点pre(即反转链表的头节点)
2. 递归后继节点，记录返回值(即反转链表的头节点)为res;
3. 修改当前节点cur引用指向前驱节点pre;
4. 返回反转链表的头节点res;

reverseList(head)函数：

调用并返回recur(head，null)。传入null是因为反转链表后，head节点指向null;

复杂度分析：

• 时间复杂度O(N):遍历链表使用线性大小时间。
• 空间复杂度O(N):遍历链表的递归深度达到N，系统使用O(N)大小额外空间。

class Solution:
	def reverseList(self, head):
		def recur(cur, pre):
            if not cur: return pre
            res = recur(cur.next, cur)
            cur.next = pre
            return res
		return recur(head, None)