有一个带头结点的单链表L,设计一个算法将L逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点,如此等等。
时间: 2024-09-29 10:04:42 浏览: 15
要逆置一个带头结点的单链表,可以采用迭代或递归的方法。这里提供一种迭代的方法:
1. 定义三个指针:prev、current和next。初始时,prev指向头结点,current也指向头结点,而next为空。
2. 当current不为null时,执行以下步骤:
a. 将current的下一个节点赋值给next。
b. 将current的next指针更新为prev,完成一次反转操作。
c. 更新prev和current,让它们分别移动到当前节点和next节点的位置。
d. current = next; (继续处理下一个节点)
3. 执行完上述循环后,current会变为null,此时prev就是新的头结点,链表已经被成功逆置。
```python
def reverseList(head):
prev = None
current = head
while current is not None:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
return prev # 返回新的头结点
```
相关问题
算法设计题:有一个带头结点的单链表L,设计一个算法将L逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点,如此等等。
要反转一个带头结点的单链表,可以采用迭代或者递归的方式来实现。这里提供一种迭代的方法:
1. 定义三个指针:prev、current 和 next,分别表示前驱、当前和后继节点。初始化时,prev 和 current 都设置为头节点,next 设为 null。
2. 使用一个 while 循环,当 current 不为 null 时执行以下操作:
a. 将当前节点的 next 指向 prev:`current->next = prev;`
b. 更新前驱节点为当前节点:`prev = current;`
c. 移动当前节点到后一个位置:`current = current->next;`
3. 循环结束后,prev 就指向了新的头节点,因为我们在每次迭代中都是把当前节点的 next 指向了前驱。
以下是 Python 的示例代码:
```python
def 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
```
有一个带头结点的双链表L,设计一个算法将其所有元素逆置,即第1个元素变为最后一个元素,第2个元素变为倒数第2个元素,…,最后一个元素变为第1个元素。
在双链表中实现元素逆置的过程通常需要遍历整个列表并将每个节点的前驱指针和后继指针临时交换。以下是一个简单的步骤描述:
1. 定义两个指针,`prev` 和 `current`,初始化它们都为头结点 `L`(因为当前节点和前一个节点都是头结点本身)。
2. 创建一个临时指针 `temp`,用于存储 `current` 的后继节点。
3. 进行循环,直到 `current` 为 `null` 或者 `null`(表示链表结束):
a. 将 `current` 的后继节点赋值给 `temp`。
b. 更新 `current` 的后继指针,使其指向 `prev`。
c. 移动 `prev` 和 `current` 向前,让 `prev` 现在指向 `temp`,`current` 指向下一个节点。
4. 当循环结束时,`prev` 就会变成新的头结点,因为它最后指向了原来的尾部。
下面是伪代码形式的实现:
```python
function reverseList(L):
prev = L
current = L.next
while current is not null:
temp = current.next
current.next = prev
prev = current
current = temp
return prev # 返回新头结点
```