【算法入门11】反转链表

【算法入门11】反转链表

核心考点：链表操作，思维缜密程度

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

解析一：（三指针法） 利用三个指针进行链表的反转：

left，mid，right依次指向第一个结点，第二个结点和第三个结点。让mid指向的结点指向left。left，mid，right统一向右移动。反复指向步骤2和步骤3，直到right指向链表表尾，即nullptr。再让mid指向的结点指向left。最后让第一个结点指向空，即nullptr。

注意： 当链表为空或链表当中只有一个结点时，链表无需反转。

动图演示：

/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution {public: ListNode* ReverseList(ListNode* pHead) { if (pHead == nullptr || pHead->next == nullptr) //链表为空或链表只有一个结点，无需反转 return pHead; ListNode* left = pHead; ListNode* mid = left->next; ListNode* right = mid->next; while (right != nullptr) { //mid指向left mid->next = left; //left,mid和right统一向右移动 left = mid; mid = right; right = right->next; } mid->next = left; //mid指向left pHead->next = nullptr; //第一个结点指向nullptr return mid; //返回新链表的表头，也就是此时的mid }};

解析二：（头插法） 还可以使用头插的方式进行链表的反转，具体过程就是依次取原链表的第一个结点头插到一个空链表当中，当原链表当中的结点全部被取完时，原来的空链表就是反转后的新链表。

动图演示：

/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution {public: ListNode* ReverseList(ListNode* pHead) { if (pHead == nullptr || pHead->next == nullptr) //链表为空或链表只有一个结点，无需反转 return pHead; ListNode* newHead = nullptr; while (pHead != nullptr) { //从原链表获取第一个结点 ListNode* p = pHead; pHead = pHead->next; //将该结点头插到新链表 p->next = newHead; newHead = p; } return newHead; //返回新链表的表头 }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。