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

1、介绍

输入一个链表的头结点，按照链表从尾到头的顺序返回一个vector数组。

2、题解

本人写法：先按照顺序把所有元素入栈，然后再出栈把值写入vector数组中。
（因为是翻转，所以本人第一时间想到了栈。加上忘记了vector1.insert(vector1.begin(),value) 可以把数据添加到开头，所以写的比较麻烦。）

#include <iostream>
#include <stack>
#include <vector>

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int v = 0,ListNode* n = nullptr)
        :val(v),next(n)  {}
};

std::vector<int> printListFromTailToHead(ListNode* head)
{
    int elemCount = 0;
    std::stack<ListNode*> nodes;
    if(head == nullptr){
        std::cout<<"链表为空";
        std::vector<int> v(0);
        return v;
    }

    //所有元素入栈
    ListNode* temp = head;
    while(temp != nullptr){
        nodes.push(temp);
        temp = temp->next;
        elemCount++;
    }

    //出栈，并把元素添加进vector数组中
    std::vector<int> vals(elemCount);
    int index = 0;
    while(!nodes.empty()){
        int num = (nodes.top())->val;
        vals[index++] = num;
        nodes.pop();
    }
    return vals;
}

更好点的写法：

std::vector<int> printListFromTailToHead(ListNode* head)
{
    std::vector<int> vals;
    if(head != nullptr)
    {
        ListNode* temp = head;
        while(temp != nullptr){
            //直接把值添加到数组开头，相当于翻转了
            vals.insert(vals.begin(),temp->val);
            temp = temp->next;
        }
    }
    return vals;
}

3、变形题

输入链表头结点，把链表翻转后返回。

本人写法：利用了vector，所以增加了空间开销

ListNode* printListFromTailToHead(ListNode* head)
{
    if(head != nullptr){
        //先翻转链表
        std::vector<ListNode*> nodes;

        ListNode* temp = head;
        while(temp != nullptr){
            nodes.insert(nodes.begin(),temp);
            temp = temp->next;
        }

        //再翻转next指向
        for(int i=0;i<nodes.size()-1;i++){
            nodes[i]->next = nodes[i+1];
        }
        nodes[nodes.size()-1]->next = nullptr;
        return nodes[0];
    }
    return head;
}

更好点的写法：定义三个指针分别指向当前结点、前一个结点、后一个结点。然后翻转每一个指向，最后返回第一个结点（刚开始的头结点）。

ListNode* printListFromTailToHead(ListNode* head)
{
    //当前节点、前一个结点、后一个结点、翻转后的头结点
    ListNode* currentNode = head;
    ListNode* frontNode = nullptr;
    ListNode* nextNode = nullptr;
    ListNode* newHead = nullptr;

    while(currentNode != nullptr){
        //如果是最后一个结点，赋值后退出
        if(currentNode->next == nullptr){
            currentNode->next = frontNode;
            newHead = currentNode;
            break;
        }
        nextNode = currentNode->next;
        //翻转
        currentNode->next = frontNode;
        frontNode = currentNode;
        currentNode = nextNode;
        nextNode = currentNode->next;
    }
    return newHead;
}

4、新知识和不足

做完发现自己vector和STL中常用容器用法不是很熟练。
打算补一下。
先立个flag，学完写博客记录下。

剑指Offer---面试题6---单链表反转

原文：https://www.cnblogs.com/Fflyqaq/p/12016714.html