[TOC]

1. 题目描述

• 描述

  输入一个链表，反转链表后，输出新链表的表头。

• 示例1

  输入：
  {1,2,3}
  复制
  返回值：
  {3,2,1}

2. 解题思路

• 思路1, 递归反转

  处理完成后内部传出头指针, 然后将当前节点挂接到自己的子节点上面;

• 思路2, 缓存方案

  好处是不会因递归深度而爆栈, 用vector存储所有节点, 然后从后往前遍历重新拼接即可;

PS: 实际方案选择, 可以根据题目要求, 和自己的习惯选择实现起来最快, 或者 出题人要求的算法来写代码;

3. 详细代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead == nullptr) {
            return pHead;
        }
        ListNode* head = pHead->next;
        vector<ListNode*> nodes{pHead};
        while (head) {
            nodes.push_back(head);
            head = head->next;
        }
        for (int i = nodes.size()-1; i > 0; i--) {
            nodes[i]->next = nodes[i-1];
        }
        nodes[0]->next = nullptr;
        return nodes.back();
    }
};

4. 运行结果