牛客题霸反转链表C++版题解

牛客题霸NC78反转链表
题目链接：https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=188&&tqId=36311&rp=1&ru=/ta/job-code-high-week&qru=/ta/job-code-high-week/question-ranking

我的题解：
首先要明确这道题总体的思路是通过借助指针操作来使链表反转，我们首先考虑非初始状态下的情景，如图1所示，原始的链表在被反转的过程中，可以将它看作两部分：已进行反转的部分和尚未反转的部分，我们设“当前指针cur”指向的节点是未反转部分的头结点，也就是说，接下来我们想要将这个结点要添加到已反转的部分且该结点要作为已反转部分的头结点。
图1
这就很容易联想到我们首先要找到*已反转部分的头指针，我们让“前驱指针pre”指向已反转部分的头结点，就“已知”了这个头指针，让“当前指针cur”的next指向已反转部分的头指针，即cur->next=pre，就将cur指向的当前结点和之前已反转部分的头结点连了起来，此时cur成为了已反转部分的头指针，如图2所示。
图2
那么问题来了，我们找不到未反转部分的头指针了呀，所以还需要一个“后继指针nex”来保存“当前指针cur”指向的结点还未进入已反转部分时的下一个结点，也就是在进行cur->next=pre之前，先要保存一下当前即将被操作的结点的下一个结点的地址**，即先要nex=cur->next，如图3、图4所示。
这样我们一共需要三个指针：指向已反转部分头结点的pre，指向未反转部分头结点的cur和为了反转后依然能找到未反转部分而指向cur->next的nex。
图3
图4
想要进行下一次反转操作时，之前的cur就要作为pre了，所以让pre=cur，cur是现在的nex，所以让cur=nex，nex则需要继续后移一个，即nex=cur->next，如图5所示。然后就可以进行下一次的反转操作了，令cur->next=pre，再去对pre、cur、nex重新赋值，如此循环往复直到当前指针cur指向为NULL，说明原始链表中的结点已经全部属于已反转后的链表了。
图5
下面我们从初始状态时来分析，初始状态时，还没有已反转的部分，所以pre指向NULL，cur指向原始链表的头结点pHead，所以程序初始化为pre=NULL,cur=pHead,nex=pre->nex，虽然pre为空但是其实原理同上面一样，初始化之后进行while循环，循环内先让cur->next指向pre，此时链表就已经分成了已反转和未反转的两部分，和一开始的讲解对应上了，之后一次次循环把两部分连起来就好了。再次反转前的pre就是cur，cur变成nex，nex也相应后移一位，如图6所示，然后进行下一次循环，通过cur->next=pre，将cur指向的当前结点加入已反转部分中。直到cur指向空时，说明当前已经没有结点需要再加入已反转的部分了，pre即是反转完成后链表的头结点，返回pre即可，如图7所示。
图6
图7
按照以上思路代码如下：
class Solution {
public:
ListNode ReverseList(ListNode* pHead) {
ListNode *pre = NULL;
ListNode *cur = pHead;
ListNode *nex = cur->next; //这里也可以初始化为NULL，但循环内部要先对nex赋值
while (cur) {
cur->next = pre;
pre = cur;
cur = nex;
nex = cur->next;
}
return pre;
}
};

其中，nex初始化时也可以初始化为NULL，此时在while循环中要先进行nex = cur->next;，这样可以保证最后一次循环结束时，cur和nex都是指向NULL，而我这种写法，最后nex指向了NULL的next，有点怪怪的感觉，但是这样写代码也可以通过，而且与我之前写的思路比较吻合，nex一直都是cur->next。