链表的逆置
时间: 2023-07-10 14:19:39 浏览: 45
链表的逆置指的是将链表中的节点顺序颠倒,即原来的最后一个节点变为新链表的第一个节点,原来的第一个节点变为新链表的最后一个节点。下面是一种递归的实现方式:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head: ListNode) -> ListNode:
if not head or not head.next:
return head
new_head = reverseList(head.next)
head.next.next = head
head.next = None
return new_head
```
这段代码中,我们首先判断链表是否为空或只有一个节点,如果是,直接返回原链表。否则,我们递归调用 `reverseList` 函数,将当前节点的下一个节点作为新链表的头节点,然后将当前节点作为新链表尾部的节点。
具体实现中,我们先递归调用 `reverseList(head.next)`,得到新链表的头节点 `new_head`。然后将当前节点 `head` 的下一个节点 `head.next` 的 `next` 指针指向 `head`,完成当前节点与其下一个节点的逆置。最后将当前节点 `head` 的 `next` 指针设为 `None`,避免出现环,返回新链表的头节点 `new_head`。