用递归实现翻转链表,给出代码和详细的注释
时间: 2024-05-10 08:20:14 浏览: 79
递归翻转链表的基本思路是:先将当前节点的下一个节点递归翻转,然后将当前节点插入到翻转后的链表的末尾。具体步骤如下:
1. 判断当前节点是否为空或者下一个节点为空,如果是,直接返回当前节点。
2. 递归翻转当前节点的下一个节点。
3. 将当前节点插入到翻转后链表的末尾。
4. 将当前节点的下一个节点置为空,防止出现环。
代码如下:
```python
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
new_head = self.reverseList(head.next) # 递归翻转当前节点的下一个节点
head.next.next = head # 将当前节点插入到翻转后链表的末尾
head.next = None # 将当前节点的下一个节点置为空,防止出现环
return new_head
```
注释如下:
```python
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
new_head = self.reverseList(head.next) # 递归翻转当前节点的下一个节点
head.next.next = head # 将当前节点插入到翻转后链表的末尾
head.next = None # 将当前节点的下一个节点置为空,防止出现环
return new_head
```
阅读全文