算法-链表反转操作

淩亂°似流年 2022-06-11 05:26 161阅读 0赞

**题目：**  
定义一个函数，输入一个链表的头结点，反转该链表并输出反转后的头结点。链表定义如下：

struct ListNode
    {
      int value;
      ListNode *next;
    };

**解题思路：**

原本我们有一个这样的链表，并且知道他的头结点，即存放数值1的节点的地址。  
![这里写图片描述][SouthEast]

链表反转后的效果：

![这里写图片描述][SouthEast 1]

并返回新的链表的头结点，即原链表最后一个结点的地址。  
为了现实上面的功能，需要调整原链表中的指针方向，即本来结点2的next要指向结点3的地址，现在将其指向结点1的地址。要完成这个工作需要两个指针，一个指针`* pNode`指向当前遍历到的结点，一个指针`* pPrev`指向它前一个结点。

那么遍历到结点2时，就像这样：

![这里写图片描述][SouthEast 2]

此时就出现一个问题，链表已经断开了，在原链表中结点2后面的结点是哪个就不知道了（因为`* next`已经指向了结点1），为了避免这个问题，我们需要定义第三个指针`* pNext`，用来指向当前的结点的下一个结点。

剩下的工作就是遍历原链表，然后调整指针的指向，但是循环总需要一个退出条件，这个条件就是原链表的最后一个结点的`* pNext = null`

**代码实现：**

ListNode * ReverseList(ListNode * pHead)
    {
        ListNode * pRevesedHead = nullptr;//翻转后的头结点
        ListNode * pNode = pHead;//指向当前结点的指针
        ListNode * pPrev = nullptr;//指向当前结点的前一个结点的指针
        while (pNode != nullptr)//遍历原链表
        {
            ListNode * pNext = pNode->next;//定义指向当前结点下一个结点的指针并赋值
            if (pNext == nullptr)//只有一个结点的情况或者到达原链表的最后一个结点
            {
                pRevesedHead = pNode;//返回
            }
            pNode->next = pPrev;//当前结点的next指向pPrev
            //对pPrev重新赋值，这是因为第一次遍历链表时pPrev一定为null,但是随着遍历
            //pPrev的值总需要跟着变化，相对于下一个结点而言的前一个结点就是当前的结点（有点绕）
            pPrev = pNode;
            //和前面一行是一样的道理，pNode永远只指向当前的结点，但是在遍历的过程中，当前的结点
            //总要一直在向后移动（要不遍历什么呢），所以后移的结点就是pNext，就像之前说的，pNext
            //是预先保存下来的原链表的下一个结点，因为当我们执行pNode->next = pPrev链表就已经断开了
            pNode = pNext;
        }
        return pRevesedHead;
    }

额，注释越加越多，要解释明白这个简短的代码也是挺麻烦的，也说明了这个代码的质量确实很高，再贴一些图说明下吧。  
![这里写图片描述][SouthEast 3]

最后需要注意的是while里面的if判断，它有两个作用：

1 如果原链表只有一个结点的，那么直接把这个结点地址给预先定义好的反转后链表的头结点。

2 如果原链表不只有一个结点，最终也要进入if，因为遍历总有结束的时候，这时进入if后会紧跟着退出while。

测试的程序就不贴了，本来这就是个很常见的面试题，有很多资料可以找到完整的测试例程，而且自己写一个也不麻烦，在上面只是说下自己的理解。

[SouthEast]: /images/20220611/46845efac48e4436916cfb538b3040ed.png
[SouthEast 1]: /images/20220611/96d609e2b7444458acf41323e857cfad.png
[SouthEast 2]: /images/20220611/61046858fa0f4a2992d8a0e1b05f3512.png
[SouthEast 3]: /images/20220611/082405d8f50845829abc398273d86447.png