输入一个链表的头节点,从尾到头返回每个节点的值
时间: 2024-05-10 14:14:49 浏览: 7
以下是用 Python 语言实现的解法:
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def reversePrint(head: ListNode) -> List[int]:
stack = []
while head:
stack.append(head.val)
head = head.next
return stack[::-1]
```
这个解法首先遍历链表,将每个节点的值压入栈中,然后再将栈中的元素依次弹出,即可得到从尾到头的节点值列表。
相关问题
链表从尾到头反向输出
链表从尾到头反向输出可以使用多种方法实现,其中包括递归和头插法两种常见的方法。
1. 递归方法:递归的本质类似于一个栈结构,我们可以每次访问一个节点时,先递归输出后面的节点,然后再输出自身节点,这样就可以实现反向输出链表。具体实现可以参考以下代码:
void PrintListReverse(Node* head) {
if (head != nullptr) {
if (head->next != nullptr) {
PrintListReverse(head->next);
}
cout << head->val << " ";
}
}
2. 头插法方法:头插法是创建链表时的一种常见方法,每次新建的节点插入到头结点之后,这样最后一个插入的节点就成为了创建后链表的第一个节点。我们可以使用头插法来创建一个反向的链表,然后再遍历输出即可。具体实现可以参考以下代码:
void PrintListReverse(Node* head) {
Node* dummy = new Node(-1);
while (head != nullptr) {
Node* next = head->next;
head->next = dummy->next;
dummy->next = head;
head = next;
}
head = dummy->next;
while (head != nullptr) {
cout << head->val << " ";
head = head->next;
}
}
用c语言实现从尾到头反向输出带头结点单链表的值
当我们要从尾到头反向输出带头结点单链表的值时,可以使用递归的方式来实现。下面是用C语言实现的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义单链表节点结构
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 递归方式反向输出链表值
void reversePrint(ListNode* head) {
if (head->next != NULL) {
reversePrint(head->next);
}
if (head->val != -1) { // 过滤掉头结点的值
printf("%d ", head->val);
}
}
int main() {
// 创建头结点
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
head->val = -1; // 头结点的值设为-1
head->next = NULL;
// 创建链表节点
ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
node1->val = 1;
node1->next = NULL;
ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
node2->val = 2;
node2->next = NULL;
ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
node3->val = 3;
node3->next = NULL;
// 构建链表
head->next = node1;
node1->next = node2;
node2->next = node3;
// 从尾到头反向输出链表值
reversePrint(head);
// 释放内存
free(node1);
free(node2);
free(node3);
free(head);
return 0;
}
```
这段代码创建了一个带头结点的单链表,并通过递归方式实现了从尾到头反向输出链表的值。输出结果为:3 2 1。注意在递归过程中,过滤掉了头结点的值(即值为-1的节点)。