【剑指offer】从尾到头打印链表（单链表逆置 + 图解 + 单链表实现）_单链表首尾逆置c++实现

【剑指offer】从尾到头打印链表（单链表逆置）

【本题链接】
【题目描述】

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

【题意解析】
本题就是单链表逆置问题，考察了对于链表结构的掌握
【解题思路】
本题一共有两种解法，一种不改变单链表的结构，另一种改变单链表的结构。
【解法一：】
最简单的获取链表中各个节点的值，然后在数组中进行逆置操作，则可以从尾到头打印单链表，使用到C++容器中的vector和算法库中的函数reverse(array.begin(),array.end());，不改变链表结构所以比较简单
代码如下：

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> array;
        while(head)
        {
            array.push_back(head->val);
            head = head->next;
        }
        reverse(array.begin(),array.end());
        return array;
    }
}; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

【方法二：】
改变链表的结构，实现单链表的反转，使用前后指针进行操作。
步骤如下
1.首先将前后指针prev和cur都放在头节点上

2.循环，cur往后走，走到第二个节点，要实现逆置，则要将其next指针指向prev,但是若直接指向prev，则cur后面的节点丢失，所以我们使用head->next先指向cur后面的节点，这样就可以访问到下一个节点，此时再将cur -> next = prev;，完成两个节点的逆置。



最后一次

head->next为空时则翻转结束，最后红线为字符串新的节点顺序
则此时cur为头指针，遍历链表则得到翻转后的顺序。
代码如下：

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> array;
        ListNode* cur = head;
        ListNode* prev = head;
        if(head == NULL)
        {
            return array;
        }
        while(head ->next != NULL)
        {
            cur = head->next;
            head->next = cur->next;
            cur -> next = prev;
            prev = cur;
        }
        while(cur)
        {
            array.push_back(cur->val);
            cur = cur->next;
        }
        return array;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

以上便是本题的解，但是oj中链表是人家给的，在面试时，面试官可能会让你实现一个简单的单链表，然后再反转，考验你的代码能力，学医我们也应学会简单链表的实现及节点的增加。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;
//自己实现简单的单链表
typedef struct ListNode{
	int val;
	ListNode* next;
}ListNode;
typedef struct List{
	ListNode* _head;
}List;
void ListInit(List* plt){
	plt->_head = NULL;
}
void List_pushback(List* plt,int data)
{
	ListNode* newnode = new ListNode;
	newnode->val = data;
	newnode->next = NULL;
	if (plt->_head == NULL)
	{
		plt->_head = newnode;
	}
	else{
		ListNode* cur = plt->_head;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
	
}
//不改变链表结构，只是获得链表元素保存在数组中进行翻转
/*vector<int> printListFromTailToHead(List* plt) {
	vector<int> _array;
	ListNode* cur = plt->_head;
	while (cur)
	{
		_array.push_back(cur->val);
		cur = cur->next;
	}
	reverse(_array.begin(), _array.end());
	return _array;
}*/
//改变链表结构
vector<int> printListFromTailToHead(List* plt) {
	vector<int> _array;
	ListNode* head = plt->_head;
	ListNode* cur = plt->_head;
	ListNode* prev = plt->_head;
	if (plt->_head == NULL)
		return _array;
	while (head->next != NULL)
	{
		cur = head->next;
		head->next = cur->next;
		cur->next = prev;
		prev = cur;
	}
	head = nullptr;
	while (cur)
	{
		_array.push_back(cur->val);
		cur = cur->next;
	}
	return _array;
}
int main()
{
	List s;
	ListInit(&s);
	List_pushback(&s,1);
	List_pushback(&s, 2);
	List_pushback(&s, 3);
	List_pushback(&s, 4);
	vector<int> array = printListFromTailToHead(&s);
	for (int i = 0; i < (int)array.size(); i++)
	{
		cout << array[i] << ' ';
	}
	cout << endl;
	system("pause");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86