单链表逆置的概念原理(代码)
时间: 2024-09-25 11:03:45 浏览: 6
单链表逆置是指将一个已排序的单向链表的所有节点顺序反转,即原来的头节点变成最后一个节点,而原来的尾节点变成新的头节点。这通常通过迭代或递归的方式实现。以下是使用迭代的Python代码示例:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head):
prev = None
curr = head
while curr is not None:
# 保存当前节点的下一个节点
next_node = curr.next
# 将当前节点指向prev
curr.next = prev
# 移动prev和curr指针
prev = curr
curr = next_node
return prev # 返回新头节点
```
这段代码首先创建两个指针`prev`和`curr`,初始时`prev`为None,`curr`为链表的头节点。然后,在循环中,每次迭代都将`curr`的`next`指向前一个节点`prev`,接着移动`prev`和`curr`分别到下一个位置。当`curr`变为None(遍历结束),`prev`就是新的头节点。
相关问题
单链表逆置c语言代码
单链表逆置的C语言代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct ListNode {
int val;
struct ListNode* next;
};
// 单链表逆置函数
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* curr = head;
while (curr != NULL) {
struct ListNode* nextTmp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTmp;
}
return prev;
}
// 测试函数
void test() {
// 创建链表节点
struct ListNode* node1 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* node2 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* node3 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* node4 = (struct ListNode*)malloc(sizeof(struct ListNode));
// 初始化链表节点的值
node1->val = 1;
node2->val = 2;
node3->val = 3;
node4->val = 4;
// 构建链表关系
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
// 输出原始链表
printf("原始链表:");
struct ListNode* curr = node1;
while (curr != NULL) {
printf("%d ", curr->val);
curr = curr->next;
}
// 单链表逆置
struct ListNode* newHead = reverseList(node1);
// 输出逆置后的链表
printf("\n逆置后的链表:");
curr = newHead;
while (curr != NULL) {
printf("%d ", curr->val);
curr = curr->next;
}
// 释放内存
free(node1);
free(node2);
free(node3);
free(node4);
}
int main() {
test();
return 0;
}
```
单链表逆置代码
以下是单链表逆置的代码,希望能够帮到您:
```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* curr = head;
while (curr != NULL) {
ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
// 定义测试函数
void test() {
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
ListNode* newHead = reverseList(head);
while (newHead != NULL) {
cout << newHead->val << " ";
newHead = newHead->next;
}
}
// 主函数
int main() {
test();
return 0;
}
```
注:以上代码是使用 C++ 编写的。