编写算法将单链表中元素的次序完全颠倒
时间: 2024-09-12 22:02:47 浏览: 21
编写算法将单链表中元素的次序完全颠倒,可以采用迭代的方式来实现。核心思想是遍历原始链表,每次取出一个节点,将其插入到新链表的头部,从而达到顺序颠倒的效果。下面是具体的步骤和示例代码:
1. 初始化三个指针:`previous`(前指针),`current`(当前指针)和`next`(后指针)。初始时,`previous`为`null`,`current`为链表的第一个节点。
2. 遍历原始链表,对于每个节点:
a. 在插入之前,先保存下一个节点,即`next = current.next`。
b. 将当前节点的`next`指针指向`previous`,这样就将当前节点插入到了新链表的头部。
c. 移动`previous`和`current`指针,`previous = current`,`current = next`。
3. 当遍历结束时,`current`将变为`null`,此时`previous`指向的就是新的链表的头节点。
以下是用Python语言实现的代码示例:
```python
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
def reverseList(head):
previous = None
current = head
while current is not None:
next = current.next
current.next = previous
previous = current
current = next
return previous
```
这段代码中,`ListNode`定义了链表的节点结构,`reverseList`函数实现了链表的翻转。最后返回的`previous`就是新链表的头节点。