每日一题 剑指offer（反转列表）

编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化和锻炼自己的编程能力（最起码不会忘记编程）

特别说明：编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法，所以提供的代码不一定是最优解，但是本文提供的编程代码均为通过测试代码。

反转列表

题目描述

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

列表格式如下

1struct ListNode {
2        intval;
3        structListNode *next;
4        ListNode(intx) :
5           val(x),next(NULL) {
6        }
7
8};


解析

我们可以利用递归的方法来实现这个反转功能，它利用递归走到链表的末端，然后再更新每一个node的next 值，实现链表的反转。而newhead 的值没有发生改变，为该链表的最后一个结点，所以，反转后，我们可以得到新链表的head。

代码

1class Solution {
2public:
3    ListNode* ReverseList(ListNode* pHead) {
4        //如果链表为空或者链表中只有一个元素
5        if(pHead==NULL||pHead->next==NULL) return pHead;
6        //先反转后面的链表，走到链表的末端结点
7        ListNode* pReverseNode=ReverseList(pHead->next);
8        //再将当前节点设置为后面节点的后续节点
9        pHead->next->next=pHead;
10        pHead->next=NULL;
11        return pReverseNode;
12
13    }
14};