题解 | #反转链表#

1 迭代反转链表
思路：从当前链表的首元节点开始，一直遍历至链表的最后一个节点，这期间会逐个改变所遍历到的节点的指针域，
另其指向前一个节点。
链表 1-->2-->3-->4-->5
逆链表 1<--2<--3<--4<--5
步骤：
第一步：三个节点，前中后节点，前节点指向空，中节点指向头结点head；
第二步：当当前节点不为空时，则后节点指向头结点下一个节点,当前节点指向先前节点pPreNode,
当前节点向前移动到先前节点，下一个节点移动到当前节点；
第三步：输出头结点

/
ListNode *ReverseList(ListNode *head)
{
if (pHead == nullptr) {

   return nullptr;

}

if (pHead->next == nullptr) {

   return pHead;

}

ListNode *pPreNode = nullptr;
ListNode *pCurrNode = head;

while(pCurrNode != nullptr) {

   ListNode *pNextNode = pCurrNode->next; //当前节点下一个节点存储到pNextNode
   pCurrNode->next = pPreNode; //当前节点指向先前节点pPreNode
   pPreNode = pCurrNode; // 当前节点向前移动到先前节点
   pCurrNode = pNextNode; // 下一个节点移动到当前节点

}
return pPreNode; //反转的头节点
}

2 递归反转链表
思路：和迭代反转法的思想恰好相反，递归反转法的实现思想是从链表的尾节点开始，
依次向前遍历，遍历过程依次改变各节点的指向，即另其指向前一个节点。
步骤：
第一步：从第一个循环递归到倒数第二个节点，通过倒数第二个节点指向最后一个节点，
输出的节点为最后一个节点，作为新的头节点pHeadNode；
第二步：最后一个节点指向倒数第二节点
第三步：倒数第二个指针域为空
/
ListNode *ReverseList(ListNode *head)
{
if (pHead == nullptr) {
```
   return nullptr;
```
}

if (pHead->next == nullptr) {
```
   return pHead;
```
}

ListNode *pCurrNode = head;
ListNode *pHeadNode = ReverseList(pCurrNode->next); //pCurrNode->next为倒数第二节点
pCurrNode->next->next = pCurrNode; //最后一个节点指向倒数第二个节点
pCurrNode->next = nullptr; //倒数第二个节点指向空

return pHeadNode; //反转的头节点
}

3 头插法反转链表
思路：指在原有链表的基础上，依次将位于链表头部的节点摘下，然后采用从
头部插入的方式生成一个新链表，则此链表即为原链表的反转版。
步骤：
第一步：创建一个新节点，目的创建一个新链表
第二步：保存头节点,即断开头节点，移到下一个节点
第三步：保存头节点指向一个空节点，移到下一个节点
第四步：循环

/
ListNode ReverseList(ListNode *head)
{
if (pHead == nullptr) {

   return nullptr;

}

if (pHead->next == nullptr) {

   return pHead;

}

ListNode *newHeadNode = nullptr;
ListNode *tempNode = nullptr;
while (head != nullptr) {

   tempNode = head; // 保存头节点,即断开头节点
   head = head->next; //移到下一个节点
   tempNode->next = newHeadNode; //保存头节点指向一个空节点
   newHeadNode = tempNode; //新节点，移到下一个节点

}
return newHeadNode;
}

4 就地逆置反转法
与头插法的区别：就地逆置法和头插法的实现思想类似，唯一的区别在于，头插法是通过建立一个新链表实现的，
而就地逆置法则是直接对原链表做修改，从而实现将原链表反转。
思想：从第二个节点开始到最后一个节点，依次取出来，第二个节点重新链接第一个节点，第三个节点链接第二个节点，...,第n个
节点链接第n-1个节点。
步骤：
第一步：选择2个节点，一个为前节点pPreNode，另一个为后节点pEndNode；
第二步：当后节点不为空，则前节点pPreNode（第一个节点）链接后节点pEndNode的下一个节点（第三个节点），即断开第二个节点；
pEndNode（第二个节点）链接头节点head；pEndNode节点向head节点移动；pPreNode节点向pEndNode移位。依次循环...
第三步：输出头节点head
/

ListNode ReverseList(ListNode *head)
{
if (pHead == nullptr) {
return nullptr;
}

if (pHead->next == nullptr) {
    return pHead;
}

ListNode *pPreNode = head;
ListNode *pEndNode = head->next;
while (pEndNode != nullptr) {
    pPreNode->next = pEndNode->next; //断开了第二个节点，第一个节点与第三个节点链接
    pEndNode->next = head; // 第二个节点链接第一个节点
    head = pEndNode; // 向下移位
    pEndNode = pPreNode->next; //向下移位
}
return head;

}