题目描述
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例
示例 1：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000
解答方法
方法一：双指针法
思路
定义两个指针： pre 和 ccur ；pre 在前 cur 在后。
每次让 cur的 next 指向pre，实现一次局部反转
局部反转完成之后， pre和 cur同时往前移动一个位置
循环上述过程，直至pre到达链表尾部
代码
# 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:
pre = None
cur = head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
时间复杂度
O(n)
空间复杂度
O(1)
方法二：递归
思路
使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ret .
此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
同时让当前结点的 next指针指向 NULL ，从而实现从链表尾部开始的局部反转
当递归函数全部出栈后，链表反转完成。
代码
# 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 head == None or head.next == None:
return head
ret = self.reverseList(head.next)
head.next.next = head
head.next = None
return ret
