逆转一个链表的链接方向
时间: 2024-06-21 14:00:40 浏览: 13
逆转一个链表是指将链表中的节点顺序反转,即原来的头节点变成了尾节点,而原来的尾节点变成了新的头节点。这是链表操作中的一个基础问题,通常可以通过迭代或递归两种方法来解决。
1. **迭代法**:
- 创建两个指针,一个(prev)指向当前节点的前一个节点,另一个(curr)指向当前节点。
- 初始化prev为null,curr为链表头节点。
- 当curr不为空时,执行以下操作:
- 将curr的下一个节点赋给curr的prev(即反转curr的next指针)。
- 移动curr到其prev节点(curr = curr.prev)。
- 最后,将原头节点设置为prev,完成链表的反转。
2. **递归法**:
- 定义一个辅助函数,该函数接收一个参数node,表示当前处理的节点。
- 如果node不为空,将其next节点设为当前节点,然后递归调用函数处理node的next节点。
- 函数返回时,node的next节点会指向null,然后将前一个节点的next指向当前node,完成递归过程。
- 基线条件是当node为null时,返回null。
相关问题
设计一个算法,将链表中所有结点的链接方向原地逆转
可以使用三个指针来实现链表的原地逆转。具体步骤如下:
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;
}
```
设计一个算法,遍历一趟,将链表中的结点链接方向逆转
可以使用三个指针 prev、curr 和 next,其中 prev 表示当前结点的前一个结点,curr 表示当前结点,next 表示当前结点的后一个结点。每次迭代时,将 curr 的 next 指针指向 prev,然后将 prev、curr 和 next 向右移动一个结点,直到遍历完整个链表。
具体实现的代码如下:
```
void reverseLinkedList(Node* &head) {
Node* prev = nullptr;
Node* curr = head;
while (curr != nullptr) {
Node* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head = prev;
}
```
其中 head 表示链表的头结点,这里使用引用传递以便修改链表的头结点。时间复杂度为 O(n),空间复杂度为 O(1)。
相关推荐
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)