面试题6-从尾到头打印链表

ゝ一世哀愁。 2022-03-10 02:48 111阅读 0赞

# 一、题目 #

### **       题目：**输入一个链表的头结点，从尾到头反过来打印出每个结点的值。 ###

# 二、题目分析 #

###         遍历链表的顺序是从头到尾的顺序，可输出的顺序却是从尾到头。也就是说第一个遍历到的结点最后一个输出，而最后一个遍历到的结点第一个输出。这就是典型的“**后进先出**”，我们可以用栈实现这种顺序。每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，此时输出的结点的顺序已经反转过来了。 ###

# 三、代码实现 #

//题目输入一个链表的头结点，从尾到头反过来打印每个节点的值
    #include <iostream>
    #include <string>
    #include <vector>
    #include <stack>
    using namespace std;
    
    //链表节点的定义类
    struct ListNode {
    	int data;//数值
    	ListNode* next;//下一个节点的指针
    	ListNode():data(0), next(nullptr) {}//无参构造函数
    	ListNode(int d):data(d),next(nullptr){}//有参构造函数
    };
    
    class List {
    public:
    	List(int a[], int n);//构造函数
    	~List();//析构函数
    	void show();//从头到尾打印链表
    	void Print();//从尾到头打印链表----采用栈结构
    private:
    	ListNode* copyList(ListNode* &top, int a[], int n);//将数组元素插入到链表中
    	void deleteList(ListNode* &top);//删除链表
    	ListNode* topNode;
    };
    //将数组元素插入到链表中
    ListNode* List::copyList(ListNode* &top, int a[], int n) {
    	top = new ListNode;//创建头结点
    	ListNode* first = top;
    	for (int i = 0; i < n; ++i) {//循环将数组中的元素赋值到链表中
    		first->next = new ListNode(a[i]);
    		first = first->next;
    	}
    	return top;
    }
    //删除链表
    void List::deleteList(ListNode* &top) {
    	ListNode* p = top->next;
    	ListNode* q;
    	while (p) {
    		q = p->next;
    		delete p;
    		p = q;
    	}
    	top->next = nullptr;
    }
    //构造函数
    List::List(int a[], int n) {
    	topNode = copyList(topNode, a, n);
    }
    //析构函数
    List::~List() {
    	deleteList(topNode);
    }
    //从头到尾打印链表
    void List::show() {
    	ListNode* p = topNode->next;
    	while (p) {
    		cout << p->data << " ";
    		p = p->next;
    	}
    	cout << endl;
    }
    //从尾到头打印链表
    void List::Print() {
    	stack<int> s;//创建栈
    	ListNode* p = topNode->next;
    	while (p) {
    		s.push(p->data);//将链表中的元素存入栈中
    		p = p->next;
    	}
    	while (!s.empty()) {//从栈中依次取出元素
    		cout << s.top() << " ";
    		s.pop();
    	}
    	cout << endl;
    }
    
    int main(){
    	int a[] = { 1,2,3,4,5 };
    	int n = 5;
    	List l(a,n);
    	l.Print();
    	system("pause");
    	return 0;
    }