C++程序 不实际颠倒的链表反转

C++程序 不实际颠倒的链表反转

给定一个链表,使用递归函数输出它的反转顺序。例如,如果给定的链表是 1->2->3->4,则输出应该是 4->3->2->1。

请注意,问题只涉及打印反转结果。如果要颠倒列表本身,请参阅此处。

难度: 新手

C++程序 不实际颠倒的链表反转

算法:

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) 的调用栈空间

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例