Problem: 206. 反转链表

文章目录

• 思路
• 解题方法
• 复杂度
• Code

思路

递归求解

解题方法

递归过程

1. 当链表为空或者只有一个结点的时候，我们不需要任何操作，因为它已经是反转的了。 if(!head ||!head->next ) return head;
2. 如果链表是多与一个结点，我们将问题简化为反转从第二个结点开始的子链表。
   if(!head ||!head->next ) return head;
3. 当递归调用返回时，我们拥有了反转后子链表的头部 new_head。但是，当前的 head 节点仍然指向它原始的下一个节点。为了反转它，我们让 head.next.next 指向 head，这样 head 就变成了它原始下一个节点的下一个节点。
4. 断开原始连接：我们设置 head.next = None，这样就确保了链表不会形成循环。

以1->2->3->4->5 为例。
首先，我们调用 reverse_list(1)，其中 1 是链表的头部。

进入函数，首先检查基本情况，因为链表有多个节点，所以我们继续。
接着，进行递归调用 reverse_list(2)。
现在，我们调用 reverse_list(2)。

同样，我们检查基本情况，因为链表有多个节点，所以我们继续。
接着，进行递归调用 reverse_list(3)。
同理，我们调用 reverse_list(3)，然后调用 reverse_list(4)，再然后调用 reverse_list(5)。

当我们调用 reverse_list(5) 时，我们到达链表的末尾。

对于基本情况，因为 5 的下一个节点是 None，所以我们直接返回 5。
这里的递归开始“展开”。
返回到 reverse_list(4) 的调用：

我们有 new_head 指向 5。
接着，我们修改 4 的下一个节点（也就是 5）的 next 指针，使其指向 4，即 head.next.next = head。
然后断开 4 的 next 指针。
最后，返回 new_head，即返回 5。
同样的逻辑适用于 reverse_list(3)、reverse_list(2) 和 reverse_list(1) 的调用。

在递归“展开”时，链表的反转实际上是在每一层递归调用中逐步完成的，从链表的末尾开始，直到头部。

最后的结果是 5->4->3->2->1。

复杂度

• 时间复杂度:

对于链表中的每个节点，我们进行了一次递归调用。因此，如果链表有 n 个节点，我们会进行 n 次递归调用。时间复杂度：

• 空间复杂度:

递归调用会使用栈，在最坏的情况下，如果链表有n个结点，就会有n层递归，栈的深度是n,空间复杂度：

Code

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head ||!head->next ) return head; 

        ListNode* newHead = reverseList(head->next)  ; 
        head->next->next = head ; 
        head->next = NULL; 
        return newHead ; 


    }
};

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    if not head or not head.next:
        return head
    new_head = reverse_list(head.next)
    head.next.next = head
    head.next = None
    return new_head


node5 = ListNode(5)
node4 = ListNode(4, node5)
node3 = ListNode(3, node4)
node2 = ListNode(2, node3)
head = ListNode(1, node2)

# 反转
reversed_head = reverse_list(head)


result = []
while reversed_head:
    result.append(reversed_head.val)
    reversed_head = reversed_head.next
result