剑指offer(c++)-04.从尾到头打印链表
从尾到头打印链表
1. 前景知识：
链表应该是面试时被提及最频繁的数据结构。链表的结构很简单，它由指针把若干个结点连接成链状结构。链表的创建、插入结点、删除结点等操作都只需要20行左右的代码就能实现，其代码量比较适合面试。
链表是一种动态数据结构，是因为在创建链表时，无须知道链表的长度。当插入一个结点时，只需要为新结点分配内存，然后调整指针的指向来确保新结点被链接到链表当中。内存分配不是在创建链表时一次性完成，而是每添加一个结点分配一次内存。由于没有闲置的内存，链表的空间效率比数组高。
由于链表中的内存不是一次性分配的，因而我们无法保证链表的内存和数组一样是连续的。因此如果想在链表中找到它的第i个结点，我们只能从头结点开始，沿着指向下一个结点的指针遍历链表，它的时间效率为O（n）。而在数组中，我们可以根据下标在O（1）时间内找到第i个元素。。
2. 链表相关题目（摘自：剑指offer）:
面试题5：“从尾到头输出链表”、
面试题13：“在O（1）时间删除链表结点”、
面试题15：“链表中的倒数第k个结点”、
面试题16：“反转链表”、
面试题17：“合并两个排序的链表”、
面试题 37：“两个链表的第一个公共结点”等）
面试题26：“复杂链表的复制”，链表中的结点中除了有指向下一个结点的指针，还有指向任意结点的指针，这就是复杂链表。
面试题27：“二叉搜索树与双向链表”，链表中的结点中除了有指向下一个结点的指针，还有指向前一个结点的指针。这就是双向链表。
面试题45：“圆圈中最后剩下的数字”，把链表的末尾结点的指针指向头结点，从而形成一个环形链表。
3. 题目：
面试题5 从尾到头打印链表： 输入一个链表的头结点，从尾到头反过来打印出每个结点的值。链表信息如下：
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */
4. 解题方法：
解题思想1-递归思想：
- 递归思想需要明确：递和归
- 递：下一结点即 head->next，
- 递结束判断条件：if( head == NULL ) return outvalue
- 归：返回该节点值即head->val
- 建立vector存储返回结点的val，并在每次递归调用后返回该值即return outvalue。
// 递归算法代码如下：
// head: 输入链表头
// outvalue: 返回链表值
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> outvalue;
if(head == NULL)
return outvalue;
outvalue = printListFromTailToHead(head ->next);
outvalue.push_back(head->val);
return outvalue;
}
};
解题思想2-反转链表：
- 反转链表示例：输入: 1->2->3->4->5->NULL，输出: 5->4->3->2->1->NULL
- 需要三个结点变量，1.当前待反转结点tmp,2.正在反转的结点now,3.正在反转结点的前一个结点pre
- now = head ，tmp = now->next，now->next = pre，pre = now，now = tmp。
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
// nullptr：c++11中关键字表示空指针
ListNode* pre = nullptr; // pre:正在反转结点的前一个结点
ListNode* now = head; // now:当前正在反转的结点
ListNode* tmp = now; // tmp:还未反转的第一个结点
while(now){
tmp = now->next;
now->next = pre;
pre = now;
now = tmp;
}
vector<int> outvalue;
// 正序遍历单链表，将值压入vector，然后输出
while(pre){
outvalue.push_back(pre->val);
pre = pre->next;
}
return outvalue;
}
};