设l为带头结点的单链表,编写算法实现从尾到头反向输出每个结点的值
时间: 2023-05-31 18:20:25 浏览: 161
3-2 试编写一个算法,在带表头结点的单链表中寻找第i个结点.doc
### 回答1:
可以使用递归的方法,在递归函数中先访问下一个结点,再输出当前结点的值,从而实现从尾到头的反向输出。代码如下:
```
void ReversePrint(ListNode* pHead)
{
if(pHead != NULL)
{
ReversePrint(pHead->next);
cout << pHead->val << endl;
}
}
```
### 回答2:
从尾到头反向输出单链表的每个节点值是一个经常被要求的算法题目。解决这个问题的方法可以是使用递归或是利用栈的特性。
首先,我们可以考虑使用递归来解决这个问题。递归的思路是先访问链表的尾节点,然后倒着递归输出每个节点值。因此,代码可以像下面这样编写:
```python
def printListReverse(head):
if head is None:
return
else:
printListReverse(head.next)
print(head.val)
```
其中,head是链表的头节点,printListReverse函数用于打印链表中的每个节点值,如果链表为空,直接返回;否则递归打印链表中的节点值。
另一种方法是利用栈的特性。当遍历链表时,遍历到的每一个节点都被放入栈中,然后再依次弹出栈顶节点并输出,以此实现链表逆序输出的需求:
```python
def printListReverse(head):
if head is None:
return
else:
stack = []
while head:
stack.append(head.val)
head = head.next
while stack:
print(stack.pop())
```
其中,while head循环将所有节点放入栈中,while stack循环将节点从栈中弹出并输出。
以上是两种解决方法,都可以达到从尾到头反向输出每个节点值的效果。但是,使用栈更容易理解,递归也需要考虑递归栈的大小,在面对大数据时,容易栈溢出。因此,建议使用栈的方法来反转单链表。
### 回答3:
要实现从尾到头反向输出单链表每个结点的值,可以借助栈这种数据结构,用栈存储单链表中每个结点的值。具体实现步骤如下:
1. 定义一个栈,用来存储单链表中的结点值;
2. 遍历单链表,将每个结点的值依次压入栈中;
3. 弹出栈中的元素,即可实现从尾到头反向输出单链表每个结点的值。
下面是C++代码实现:
```
#include <iostream>
#include <stack>
using namespace std;
// 定义带头结点的单链表结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 从尾到头反向输出单链表每个结点的值
void reversePrintList(ListNode* head) {
if (head == NULL) {
return;
}
stack<int> s; // 定义栈,用来存储单链表中的结点值
ListNode* cur = head->next; // 从头结点的下一个结点开始遍历单链表
while (cur != NULL) {
s.push(cur->val); // 将每个结点的值压入栈中
cur = cur->next;
}
while (!s.empty()) { // 弹出栈中的元素,即可实现从尾到头反向输出单链表每个结点的值
cout << s.top() << " ";
s.pop();
}
}
int main() {
// 创建带头结点的单链表
ListNode* head = new ListNode(0);
ListNode* cur = head;
for (int i = 1; i <= 5; i++) {
ListNode* node = new ListNode(i);
cur->next = node;
cur = node;
}
// 调用函数输出单链表每个结点的值
reversePrintList(head);
return 0;
}
```
运行结果为: `5 4 3 2 1`。
阅读全文