设计一个算法,逆转一个链表的链接方向。 例如:原始链表:1 -> 2 -> 3 -> 4 -> 5 反转后:5 -> 4 -> 3 -> 2 -> 1
时间: 2024-07-02 15:00:34 浏览: 11
要设计一个算法逆转一个链表的链接方向,你可以使用迭代或递归的方式来实现。这里是一个使用迭代方法的示例:
**迭代法(节点指针):**
1. 定义两个指针,一个(prev)初始化为 NULL,另一个(current)初始化为链表头节点。
2. 当 current 不为 NULL 时,执行以下操作:
a. 保存当前节点的下一个节点(next_node = current->next)。
b. 将当前节点的 next 指向 prev(current->next = prev)。
c. 更新 prev 为当前节点(prev = current)。
d. 移动 current 到 next_node(current = next_node)。
3. 当 current 为空时,prev 就是新的头节点,此时链表反转完成。
**伪代码表示:**
```
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
```
**相关问题--:**
1. 迭代法和递归法在链表反转中的区别是什么?
2. 在这个算法中,为什么要用两个指针?
3. 如果链表非常长,这种方法的时间复杂度是多少?
相关问题
设计一个算法,逆转一个链表的链接方向。 例如:原始链表:1 -> 2 -> 3 -> 4 -> 5 反转后:5 -> 4 -> 3 -> 2 -> 1 线性表写
要设计一个算法来逆转一个链表的链接方向,你可以使用迭代或递归的方式来实现。这里我会提供一种常见的迭代方法,称为“迭代法”:
```cpp
// 假设我们有一个链表节点结构如下
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 迭代法反转链表
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) { // 如果链表为空或只有一个节点,直接返回
return head;
}
ListNode* prev = nullptr; // 前驱节点,初始化为NULL
ListNode* curr = head; // 当前节点,初始化为头节点
// 循环遍历链表
while (curr != nullptr) {
ListNode* nextTemp = curr->next; // 保存当前节点的下一个节点
curr->next = prev; // 将当前节点的next指向前一个节点
prev = curr; // 移动前驱节点到当前节点
curr = nextTemp; // 移动当前节点到下一个节点
}
return prev; // 返回新的头节点,即原链表的尾节点
}
```
相关问题--
1. 这种方法的时间复杂度是多少?
2. 在递归版本中,可能会遇到什么问题需要注意?
3. 这种方法的空间复杂度是多少?
设计一个算法,将链表中所有结点的链接方向原地逆转
可以使用三个指针来实现链表的原地逆转。具体步骤如下:
1. 定义三个指针:prev、curr、next,分别指向当前结点的前一个结点、当前结点和当前结点的后一个结点。
2. 初始化 prev 为 NULL,curr 为链表的头结点。
3. 遍历链表,每次将 curr 的 next 指向 prev,然后将 prev、curr、next 依次向后移动一个结点。
4. 当 curr 指向 NULL 时,遍历结束,此时 prev 指向原链表的尾结点,将其作为新的头结点返回即可。
具体实现代码如下:
```
void reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
ListNode* next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head = prev;
}
```