试写一算法,对单链表实现就地逆置。
时间: 2023-05-12 12:05:45 浏览: 57
可以使用三个指针来实现单链表的就地逆置,具体实现如下:
```python
def reverse_linked_list(head):
if not head or not head.next:
return head
prev, curr, nxt = None, head, head.next
while nxt:
curr.next = prev
prev, curr, nxt = curr, nxt, nxt.next
curr.next = prev
return curr
```
这个算法的时间复杂度是 O(n),其中 n 是链表的长度。
相关问题
试写一C语言算法,对单链表实现就地逆置
这里是一个基于C语言的算法,用于对单链表进行就地逆置。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表结构体
struct ListNode {
int val;
struct ListNode *next;
};
// 创建链表函数
struct ListNode *createList(int n) {
struct ListNode *head = NULL, *tail = NULL;
for (int i = 0; i < n; i++) {
int x;
printf("请输入第 %d 个节点的值: ", i + 1);
scanf("%d", &x);
struct ListNode *newNode = (struct ListNode *) malloc(sizeof(struct ListNode));
newNode->val = x;
newNode->next = NULL;
if (head == NULL) {
head = tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
}
return head;
}
// 打印链表函数
void printList(struct ListNode *head) {
printf("链表的值为:");
while (head) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
// 就地逆置函数
struct ListNode *reverseList(struct ListNode *head) {
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode *pre = NULL;
struct ListNode *cur = head;
while (cur) {
struct ListNode *next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
int main() {
int n;
printf("请输入链表的长度: ");
scanf("%d", &n);
struct ListNode *head = createList(n);
printList(head);
head = reverseList(head);
printList(head);
return 0;
}
```
算法实现的思路:
1. 如果链表为空或者只有一个节点,直接返回链表头节点。
2. 定义三个指针:pre、cur、next,分别指向当前节点的前一个节点、当前节点和下一个节点。
3. 遍历链表,每次将当前节点指向前一个节点,再将三个指针向后移动一个节点。
4. 遍历结束后,将原链表的头节点指向逆置后的链表的头节点,返回逆置后的链表的头节点。
测试结果:
```
请输入链表的长度: 5
请输入第 1 个节点的值: 1
请输入第 2 个节点的值: 2
请输入第 3 个节点的值: 3
请输入第 4 个节点的值: 4
请输入第 5 个节点的值: 5
链表的值为:1 2 3 4 5
链表的值为:5 4 3 2 1
```
试写一算法,实现对单链表的就地逆置
好的,我可以回答这个问题。以下是实现对单链表的就地逆置的算法:
1. 定义三个指针:p、q、r,分别指向当前节点、前一个节点和后一个节点。
2. 将 p 指向链表的头节点。
3. 将 q 指向 NULL。
4. 循环遍历链表,直到 p 指向 NULL:
a. 将 r 指向 p 的下一个节点。
b. 将 p 的 next 指针指向 q。
c. 将 q 指向 p。
d. 将 p 指向 r。
5. 将链表的头节点指向 q。
这样就实现了对单链表的就地逆置。