单链表反转python
时间: 2023-10-12 11:08:56 浏览: 46
可以使用以下代码实现单链表反转:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
return prev
```
这段代码中,我们使用`prev`和`curr`两个指针,其中`prev`指向上一个节点,`curr`指向当前节点。我们将当前节点的`next`指针指向上一个节点,然后将指针向后移动,直到链表末尾。最后,我们返回新链表的头部,即上一个节点。
相关问题
递归实现单链表反转python
好的,以下是递归实现单链表反转的Python代码:
```
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head: Node) -> Node:
if not head or not head.next:
return head
newHead = reverseList(head.next)
head.next.next = head
head.next = None
return newHead
```
这段代码实现了递归地将单链表反转,并返回反转后的新头结点。具体实现方法是,先递归反转子问题,即反转当前节点后面的链表,然后在反转当前节点和下一个节点之间的连接,最后返回新头结点。
数据结构实现单链表反转
单链表反转可以通过遍历链表,将每个节点的指针指向其前驱节点来实现。具体实现步骤如下:
1. 定义三个指针:pre、cur、next,分别表示当前节点的前驱节点、当前节点和后继节点。
2. 将 cur 指向链表的头节点。
3. 遍历链表,每次循环执行以下操作:
- 将 next 指向 cur 的后继节点。
- 将 cur 的指针指向 pre。
- 将 pre 指向 cur。
- 将 cur 指向 next。
4. 遍历结束后,将链表的头节点指向 pre。
下面是单链表反转的 Python 代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head: ListNode) -> ListNode:
pre, cur = None, head
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
return pre
```