四、剑指offer：06. 从尾到头打印链表

06. 从尾到头打印链表

一、题目描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

二、解题思路

方法一：用栈实现

链表只能 从前至后 访问每个节点，而题目要求 倒序输出 各节点值，这种 先入后出 的需求可以借助 栈 来实现。
算法流程：

1.入栈： 遍历链表，将各节点值 push 入栈。
2.出栈： 将各节点值 pop 出栈，存储于数组并返回。

复杂度分析：

时间复杂度 O(N)： 入栈和出栈共使用 O(N) 时间。
空间复杂度 O(N)： 辅助栈 stack 和数组 res 共使用 O(N) 的额外空间。

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head)
    {
        vector<int> v;
        stack<int> s;
        while(head!=NULL)
        {
            s.push(head->val);
            head=head->next;
        }
        while(!s.empty())
        {
            v.push_back(s.top());
            s.pop();
        }
        return v;
    }
};

方法二：使用C++自带的翻转函数reverse实现反转

（头文件为algorithm）

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head)
    {
        vector<int> v;
        while(head!=NULL)
        {
            v.push_back(head->val);
            head=head->next;
        }
        reverse(v.begin(),v.end());
        return v;
    }
};

方法三：递归法

利用递归，先递推至链表末端；回溯时，依次将节点值加入列表，即可实现链表值的倒序输出。

递归解析：

终止条件： 当 head == None 时，代表越过了链表尾节点，则返回空列表；
递推工作： 访问下一节点 head.next ；
回溯阶段：
C++： 将当前节点值 head.val 加入列表 tmp ；

复杂度分析：

时间复杂度 O(N)： 遍历链表，递归N 次。
空间复杂度 O(N)： 系统递归需要使用 O(N) 的栈空间。

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution
{
public:
    vector<int> v;
    vector<int> printListFromTailToHead(ListNode* head)
    {
        if(head!=NULL)
        {
            printListFromTailToHead(head->next);
            v.push_back(head->val);
        }
        return v;
    }
};

方法四：迭代法

①、先定义三个节点p、q、m;p头结点之后的第1个节点;q头结点之后的第2节点;m头结点之后的第3个节点。然后将头结点的next指向为null

②、判断m是否为空，实现逆序每个节点，达到直接next指向掉头；

//迭代实现链表反转
void List::reverse1()
{
	LINKNODE* p = head->next;//头结点之后的第1个节点
	LINKNODE* q = head->next->next;//头结点之后的第2节点
	LINKNODE* m = head->next->next->next;//头结点之后的第3个节点
	p->next = NULL;//将头接点之后的第1个节点的next指针置为空

	//根据m是否为空来判断 以此逆序每一个节点
	while (m) {
		q->next = p;
		p = q;
		q = m;
		m = m->next;
	}
	//将最后一个节点逆序
	q->next = p;
	//将头从新指向新的的第1个节点(之前的最后一个节点)
	head->next = q;
}

三、具体程序实现

#include <iostream>
#include <stack>
using namespace std;

class List
{
public:
	List()
	{
		create_List();
	};
	~List() { clear(); };

	void create_List();

	void insert(const int& d);

	void reverse1();

	void reverse2();

	void print();

private:

	struct LINKNODE
	{
		int data;
		LINKNODE* next;
		LINKNODE(const int& d) : data(d), next(nullptr) {}
	};

	LINKNODE* head;

	void clear()
	{
		LINKNODE* p = head;

		while (p)
		{
			LINKNODE* q = p->next;
			delete p;
			p = q;
		}
	}

};


//链表创建
void List::create_List()
{
	head = new LINKNODE(0);
}

//链表头插
void List::insert(const int& d)
{
	LINKNODE* p = new LINKNODE(d);
	p->next = head->next;
	head->next = p;
}

//迭代实现链表反转
void List::reverse1()
{
	LINKNODE* p = head->next;//头结点之后的第1个节点
	LINKNODE* q = head->next->next;//头结点之后的第2节点
	LINKNODE* m = head->next->next->next;//头结点之后的第3个节点
	p->next = NULL;//将头接点之后的第1个节点的next指针置为空

	//根据m是否为空来判断 以此逆序每一个节点
	while (m) {
		q->next = p;
		p = q;
		q = m;
		m = m->next;
	}
	//将最后一个节点逆序
	q->next = p;
	//将头从新指向新的的第1个节点(之前的最后一个节点)
	head->next = q;
}

//链表打印
void List::print()
{
	for (LINKNODE* p = head->next; p; p = p->next) {
		cout << p->data << endl;
	}
}

int main()
{
	List list;
	list.insert(2);
	list.insert(3);
	list.insert(1);
	cout << "新建链表：" << endl;
	list.print();

	cout << "反转链表1：" << endl;
	list.reverse1();
	list.print();
	
	return 0;
}

以递归法为例

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL){
        }
};

//1、递归实现
class Solution1
{
public:
    vector<int> v;
    vector<int> printListFromTailToHead(ListNode* head)
    {
        if(head!=NULL)
        {
            printListFromTailToHead(head->next);
            v.push_back(head->val);
        }
        return v;
    }
};

//2、栈实现
class Solution2
{
public:
    vector<int> printListFromTailToHead(ListNode* head)
    {
        vector<int> v;
        stack<int> s;
        while(head!=NULL)
        {
            s.push(head->val);
            head=head->next;
        }
        while(!s.empty())
        {
            v.push_back(s.top());
            s.pop();
        }
        return v;
    }
};

//使用STL算法reverse实现
class Solution3 {
public:
    vector<int> printListFromTailToHead(ListNode* head)
    {
        vector<int> v;
        while(head!=NULL)
        {
            v.push_back(head->val);
            head=head->next;
        }
        reverse(v.begin(),v.end());
        return v;
    }
};

int main()
{
    ListNode *one=new ListNode(1);
    ListNode *two=new ListNode(2);
    ListNode *three=new ListNode(3);
    ListNode *four=new ListNode(4);
    ListNode *five=new ListNode(5);
    ListNode *six=new ListNode(6);
    one->next=two;
    two->next=three;
    three->next=four;
    four->next=five;
    five->next=six;
    six->next=NULL;
    //Solution1 s;
	//Solution2 s;
	Solution3 s;
    vector<int> v;
    v=s.printListFromTailToHead(one);
    int len=v.size();
    for(int i=0;i<len;i++)
        cout<<v[i]<<' ';
    cout<<endl;
    return 0;
}

参考链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/solution/mian-shi-ti-06-cong-wei-dao-tou-da-yin-lian-biao-d/