题目

描述

给定一个单链表的头结点 pHead(该头节点是有值的，比如在下图，它的 val 是 1)，长度为 n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000

要求：空间复杂度 O(1)，时间复杂度 O(n)。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

示例 1

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

示例 2

输入：{}返回值：{}说明：空链表则输出空 

分析

考虑特殊情况

在进行问题分析过程前，我们先考虑一下特殊情况，那么在这道问题中，有哪些情况是特殊的呢？

不难发现，如下两种情况：

• 空链表，即头指针为 NULL，这种情况我们直接返回头指针即可；

• 链表只有一个节点，即 pHead->next 为 NULL，这种情况我们也直接返回头指针即可。

考虑一般情况

对于这类问题，一般都需要遍历整个链表，那我们就要考虑一下，如何在遍历一次链表的过程中，完成链表的反转，我们考虑这样一个普遍的情况如下，p(1)到 p(n-1)的节点都已经翻转了，当前遍历指针处理到 p(n)，不妨设这个指针为 pCur.

<---p(n-1) p(n)--->p(n+1)--->p(n+2)

现在，我们来想想，如果这次遍历将遍历指针移到 p(n+1)，那在这之前我们需要做什么呢？

首先：我们需要将 p(n)->next 指向 p(n-1)，这时就出现了一个问题，如果这样做我们就不知道下一个位置了，所以我们需要一个局部变量来存储 pCur 的下一个位置，不妨设为 pNext，同理，我们也需要保存一下 pCur 之前的一个位置，不妨设为 pPre;

然后：我们需要考虑怎么移动上面提到的三个指针 pPre，pCur，pNext，一个朴素的想法是按照从前往后的方式更新即可，即：

pPre = pCur;

pCur = pNext;

pNext = pNext->next;

最后：我们需要考虑遍历结束的条件，考虑到当 pCur 指向最后的数据时，pNext 是 NULL，这时再取 pNext->pNext 就会出现空指针的情况，所以我们将条件设置为 pNext ！= NULL。在这种情况下，我们要注意将最后返回值确认清楚，即 pCur。

代码演示

版本一

根据上面的描述，我们可以写出如下版本的代码：

/** * struct ListNode { *  int val; *  struct ListNode *next; * }; */
/** *  * @param pHead ListNode类  * @return ListNode类 */struct ListNode* ReverseList(struct ListNode* pHead ) {    // write code here    if(NULL == pHead || NULL == pHead->next)        return pHead;        struct ListNode *pPre = NULL;    struct ListNode *pCur = pHead;    struct ListNode *pNext = pHead->next;
    while(NULL != pNext){        pCur->next = pPre;        pPre = pCur;        pCur = pNext;        pNext = pNext->next;    }        pCur->next = pPre;    return pCur;}

注意上面版本一代码中的这两句，实际上与循环中的语句是一样的，那么我们是不是可以调整一下循环条件，然后将语句放到循环中去呢，实际上是可以的。

struct ListNode *pNext = pHead->next;...pCur->next = pPre;

可以看到，我们希望的是在循环结束条件之前，我们多执行一次 pCur->next = pPre;，其实我们只需要将条件中的 pNext 前移为 pCur 即可。

同理，对于 struct ListNode *pNext = pHead->next;，我们就需要在循环中先初始化 pNext = pCur->next.

注意我们返回值也要改变为 pCur，即所有指针都往前进行移动一个位置。

整理如下：

版本二

/** *  * @param pHead ListNode类  * @return ListNode类 */struct ListNode* ReverseList(struct ListNode* pHead ) {    // write code here    if(NULL == pHead || NULL == pHead->next)        return pHead;        struct ListNode *pPre = NULL;    struct ListNode *pCur = pHead;    struct ListNode *pNext = NULL;
    while(NULL != pCur){        pNext = pCur->next;        pCur->next = pPre;        pPre = pCur;        pCur = pNext;    }
    return pPre;}