将链表中所有结点原地逆转, 要求使用原表的结点空间。即,如果原链表中结点元素按顺序为abcde, 则逆置后链表中结点元素顺序为edcba。
时间: 2024-09-28 18:17:42 浏览: 25
将链表中的节点原地逆转,通常使用迭代或递归的方式实现。这里是一个简单的迭代方法:
1. 创建三个指针,分别命名为prev、current和next。初始化prev为NULL,current指向链表的头节点。
2. 遍历整个链表:
- 每次移动current到下一个节点(current = current->next)。
- 更新next指向前一个节点(next = current->next)。
- 然后改变当前节点的next指针,使其指向上一个节点(current->next = prev)。
3. 当遍历结束后,当前节点current会变成NULL,因为我们在遍历时更新了它的next指针。此时,prev就是新的头节点,表示链表已经逆转。
以下是伪代码描述这个过程:
```python
function reverseList(head):
prev = None
current = head
while current is not None:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev # 返回新的头节点
```
阅读全文