[206][简单][递归][双指针] 反转链表

题目描述

206. 反转链表 剑指 Offer 24. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->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 is None:
            return None
        new_head = None
        def dfs(node):
            if node.next is None:
                nonlocal new_head
                new_head = node
                return node

            new_node = dfs(node.next)
            node.next = None
            new_node.next = node
            return node

        dfs(head)
        return new_head

迭代

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        slow, fast = None, head
        while fast is not None:
            new_fast = fast.next
            fast.next = slow
            slow = fast
            fast = new_fast
        return slow