C++程序 不实际颠倒的链表反转
给定一个链表,使用递归函数输出它的反转顺序。例如,如果给定的链表是 1->2->3->4,则输出应该是 4->3->2->1。
请注意,问题只涉及打印反转结果。如果要颠倒列表本身,请参阅此处。
难度: 新手
算法:
printReverse(head)
1. 对于 head->next 调用打印反向链表
2. 打印 head->data
实现:
// C++ program to print reverse of a linked list
#include <bits/stdc++.h>
using namespace std;
// Link list node
class Node
{
public:
int data;
Node* next;
};
// Function to reverse the
// linked list
void printReverse(Node* head)
{
// Base case
if (head == NULL)
return;
// Print the list after head node
printReverse(head->next);
// After everything else is printed,
// print head
cout << head->data << " ";
}
// UTILITY FUNCTIONS
/* Push a node to linked list.
Note that this function
changes the head */
void push(Node** head_ref,
char new_data)
{
// Allocate node
Node* new_node = new Node();
// Put in the data
new_node->data = new_data;
// Link the old list off the
// new node
new_node->next = (*head_ref);
// Move the head to point to
// the new node
(*head_ref) = new_node;
}
// Driver code
int main()
{
// Let us create linked list
// 1->2->3->4
Node* head = NULL;
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
printReverse(head);
return 0;
}
// This code is contributed by rathbhupendra```
输出:
4 3 2 1
时间复杂度: O(n)
空间复杂度 : 使用递归时需要 O(n) 的调用栈空间