6-146 逆置链表
时间: 2024-06-20 21:01:28 浏览: 12
在计算机编程中,6-146 通常指的是 LeetCode 上的一个题目,名为 "Reverse Linked List"(反转链表)。这个题目要求你设计一个函数,输入一个单链表,将其节点的顺序反转,即原来的头节点变成尾节点,依次类推。
具体实现步骤如下:
1. 定义一个辅助指针 `prev` 和 `current`,初始时都指向 `None`,分别作为上一个节点和当前节点。
2. 遍历链表,从头节点开始:
- 将 `current` 的下一个节点保存到临时变量中,以防止丢失原链表的连接。
- 将 `current` 的指针更新为 `prev`,完成一次反转操作。
- 将 `prev` 指针移动到 `current` 的位置,继续处理下一次反转。
3. 当遍历到最后一个节点时,将最后一个节点的下一个节点设置为头节点(因为 `prev` 在遍历结束后指向的就是原头节点)。
4. 返回新头节点,即原链表的尾节点。
相关问题:
1. 在链表反转过程中,为什么要使用两个指针?
2. 如果链表为空,应该如何处理?
3. 这个问题的递归解法是什么样子的?
相关问题
编写算法实现带头结点单链表的就地逆置,即利用原带头节点单链表的节点空间把元素序列 a0,a1…, an-1 逆置为an-1,…,a1,a0。
思路:
- 首先判断链表是否为空,或者链表只有一个节点,则不需要逆置。
- 定义三个指针:prev、cur和next,分别指向当前节点的前一个节点、当前节点和当前节点的下一个节点。
- 在遍历链表的过程中,依次将当前节点的 next 指针指向 prev,然后依次向后移动 prev、cur 和 next 指针。
- 遍历完成后,将原头结点的 next 指针指向新的表头节点。
代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head: ListNode) -> ListNode:
if not head or not head.next:
return head
prev, cur, next = None, head.next, head.next.next
while next:
cur.next = prev
prev, cur, next = cur, next, next.next
cur.next = prev
head.next = cur
return head
```
其中,head 为带头结点的单链表头结点,返回值为逆置后的头结点。
链表逆置pta
链表逆置是一个经典的算法问题,需要对链表的指针进行操作。你可以使用三个指针prev、cur、next,分别表示当前节点的前一个节点、当前节点和当前节点的后一个节点。具体步骤如下:
1. 初始化prev为NULL,cur为链表头结点。
2. 遍历链表,每次将cur指向的节点的next指针指向prev,然后将prev、cur、next三个指针依次向后移动一个节点,直到cur指向NULL为止。
3. 最后将链表的头结点指向prev,完成链表逆置。
以下是C++实现代码:
```c++
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* cur = head;
while (cur != NULL) {
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
int main() {
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
ListNode* new_head = reverseList(head);
while (new_head != NULL) {
cout << new_head->val << " ";
new_head = new_head->next;
}
cout << endl;
return 0;
}
```
输出结果为:4 3 2 1。
相关推荐
![](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)