剑指 Offer 24. 反转链表

题目描述

https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

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

限制：

0 <= 节点个数 <= 5000

注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

解题思路

头插法
头插法利用双指针，每次遍历到的节点插在当前的head之前。这里有两个注意点：while开始前要把head.next置为None；node为None的时候，应该返回pre_node。
递归法（不推荐）
下一个要递归的节点的next等于当前的节点。递归到next为None时认定这是last_node，并在递归返回到head的时候，返回last_node。

解题代码

头插法：
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None:
            return None
        pre_node = head
        node = pre_node.next
        pre_node.next = None
        while node is not None:
            next_node = node.next
            node.next = pre_node
            pre_node = node
            node = next_node
        return pre_node

递归法：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        last_node = head
        def recurrence(node: ListNode):
            if node.next is None:
                global last_node
                last_node = node
                return node
            else:
                recurrence(node.next).next = node
                if node == head:
                    head.next = None
                    return last_node
                return node
        if head is None:
            return head
        else:
            return recurrence(head)

执行结果

头插法：56ms 15.6MB
递归法：44ms 21MB