剑指 Offer-24-反转链表

原题链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

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

image.png

解题思路：

1. 递归思路，假设head.next是已经反转过的链表的头结点ret，接着只需将head指向ret的方向反过来，即head.next.next=head，即令ret的尾结点指向head，接着令head指向空。
2. 迭代思路：参考https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/9p7s17/

Python3代码：

# 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
        ret = self.reverseList(head.next)
        head.next.next = head
        head.next = None 
        return ret

class Solution:
    def reverseList(self, head: ListNode) -> ListNode
        # 迭代
        if not head or not head.next:
            return head
        pre = None
        cur = head 
        while cur:
            tmp = cur.next
            cur.next = pre 
            pre = cur
            cur = tmp
        return pre