实现线性链表逆置的思路,即最后一个节点变成第一个结点
时间: 2023-06-20 18:09:17 浏览: 134
线性链表逆置的思路可以通过遍历链表并使用一个指针来实现。具体步骤如下:
1. 初始化三个指针变量:pre、cur、next,分别指向链表头节点的前驱节点、当前节点和后继节点。
2. 将 cur 指向链表头节点。
3. 遍历链表,每次将 cur 的后继节点赋值给 next,将 cur 的指针指向 pre,然后将 pre 指向 cur,cur 指向 next。
4. 当遍历完链表时,链表的尾节点就成为了头节点,因此需要将原链表的头节点指向空节点,将原链表的尾节点指向 pre,这样就完成了链表的逆置。
下面是具体的代码实现:
``` python
class Node:
def __init__(self, val):
self.val = val
self.next = None
def reverseList(head):
# 初始化三个指针变量
pre = None
cur = head
next = None
while cur:
# 将 cur 的后继节点赋值给 next
next = cur.next
# 将 cur 的指针指向 pre
cur.next = pre
# 将 pre 指向 cur
pre = cur
# 将 cur 指向 next
cur = next
# 将原链表的头节点指向空节点,将原链表的尾节点指向 pre
head.next = None
head = pre
return head
```
其中,head 表示链表的头节点。调用 reverseList(head) 函数即可实现链表的逆置。
阅读全文