【LeetCode_206】反转链表

刷爆LeetCode系列

• LeetCode第206题：反转链表
• github地址
• 前言
• 题目描述
• 题目与思路分析
  • 思路一：反转链表的指针指向
  • 思路二：取链表的结点，头插到新链表中
• 代码实现
  • 思路一：反转指针指向
    • 以下两种写法是保存curNext指针的方式不同
  • 思路二：取原链表中的节点，头插到新链表
  • 试错代码
• 算法代码优化
  • 思路一优化：

LeetCode第206题：反转链表

github地址

有梦想的电信狗

前言

本文用C++实现LeetCode第206题：反转链表

题目描述

• 题目链接：https://leetcode-cn.com/problems/reverse-linked-list/description/

题目与思路分析

目标分析：

1. 有单链表的头节点 head ，反转原链表
2. 返回反转后的链表的头指针
3. 提高要求：时间复杂度为O(n)，空间复杂度为O(1)

思路一：反转链表的指针指向

思路：遍历一遍链表，将当前结点的next指针，指向其前驱节点，即可实现链表的反转。最终返回链表的最后一个节点即可（原链表的最后一个结点作为新链表的头结点）

操作：

• head == nullptr时，为空链表，直接return nullptr;
• 遍历链表：
  • curNode：从头结点head开始，依次遍历链表，更改指针的指向
    • 将当前结点的next指针，指向其前驱节点，因此需要提前保存当前结点的前驱节点。
  • curPrev：记录curNode的前驱节点，方便反转指针指向，初始值为nullptr
  • curNext：提前保存curNode的后继结点，防止反转指针指向后curNode无法移动到下一个结点
• 更改指向：
  • 保存curNode的下一个结点：ListNode* curNext = curNode->next：
  • 更改当前结点的next指针：curNode->next = curPrev
  • curPrev和curNode依次向后移动：
    • curPrev = curNode;
    • curNode = curNext;
• 最终return curPrev：curPrev最后的位置就是链表的尾结点

在 while 循环内保存 curNext，保证了 curNode 一定不为空，避免了对空指针解引用可以保证一定可以取到 curNext，为空或非空

• 链表只有一个结点的情况

思路二：取链表的结点，头插到新链表中

思路：创建一个新链表，头结点为newHead，初始为nullptr。遍历原链表，将原链表中的节点依次头插到新链表中，头插后更新newHead，即可实现链表的反转，最终返回newHead

操作：

• 遍历链表：
  • curNode：从头结点head开始，依次遍历链表，进行头插操作。将当前结点的next指针，指向新链表的newHead，再更新newHead的值。之后curNode移向下一个结点。由于头插后curNode->next的值更改，不能通过curNode = curNode->next的方式移动，因此需要提前保存curNode的后继节点。
  • curNext：提前保存curNode的后继结点，防止头插后curNode无法移动到下一个结点
• 头插：
  • 保存curNode的下一个结点：ListNode* curNext = curNode->next：
  • 更改当前结点的next指针：curNode->next = newHead
  • 更新newHead的值：newHead = curNode;
  • curNode向后移动：curNode = curNext;
• 最终return newHead：newHead即为新链表的头结点

在 while 循环内保存 curNext，保证了 curNode 一定不为空，避免了对空指针解引用可以保证一定可以取到 curNext，为空或非空

代码实现

思路一：反转指针指向

以下两种写法是保存curNext指针的方式不同

• 在while循环外保存curNext指针，初始值可能为nullptr

classSolution{public: ListNode*reverseList(ListNode* head){// 空链表的情况if(head ==nullptr)returnnullptr; ListNode* curNode = head; ListNode* curPrev =nullptr; ListNode* curNext = head->next;// 链表只有一个结点的情况if(curNext ==NULL)return head;while(curNode){ curNode->next = curPrev; curPrev = curNode; curNode = curNext;// curNext可能为空，需要判断 非空时再向后移动if(curNext) curNext = curNext->next;}return curPrev;}};

• 在while循环外保存curNext指针：不涉及对curNext的解引用，即使为空也不影响

// 思路一、反转指针classSolution{public: ListNode*reverseList(ListNode* head){if(head ==nullptr)returnnullptr; ListNode* curNode = head; ListNode* curPrev =nullptr;while(curNode){// 在 while 循环内保存 curNext，保证了 curNode 一定不为空，避免了对空指针解引用// 可以保证一定可以取到 curNext ，为空或非空 ListNode* curNext = curNode->next; curNode->next = curPrev; curPrev = curNode; curNode = curNext;}return curPrev;}};

思路二：取原链表中的节点，头插到新链表

• 取链表中的节点，头插到新链表

// 思路二、取链表中的节点，头插到新链表classSolution{public: ListNode*reverseList(ListNode* head){ ListNode* newHead =nullptr,*curNode = head;while(curNode){// 提前保存 curNode 的下一个结点 ListNode* curNext = curNode->next;// 头插 curNode->next = newHead; newHead = curNode;// curNode 向后移动 curNode = curNext;}return newHead;}};

试错代码

• 初次尝试时的错误代码：
• 错误原因：
  • 第一次头插后，链表直接断开了，curNode无法移动到下一个结点

// 思路二 取结点，头插到新链表中classSolution{public: ListNode*reverseList(ListNode* head){ ListNode* newHead =nullptr; ListNode* curNode = head;while(curNode){// 错误原因，第一次头插后，链表直接断开了，curNode无法移动到下一个结点if(newHead ==nullptr){ newHead = curNode; newHead->next =nullptr;}else{ curNode->next = newHead; newHead = curNode;} curNode = curNode->next;}return newHead;}};

• 纠错后的代码：

// 思路二 取结点，头插到新链表中classSolution{public: ListNode*reverseList(ListNode* head){ ListNode* newHead =nullptr; ListNode* curNode = head;while(curNode){ ListNode* curNext = curNode->next;// 提前保存 下一个结点if(newHead ==nullptr){ newHead = curNode; newHead->next =nullptr;}else{ curNode->next = newHead; newHead = curNode;} curNode = curNext;}return newHead;}};

算法代码优化

思路一优化：

• 优化点：无需单独判断链表为空时的情况
  • 链表为空时不进入while循环，直接返回 curPrev，而 curPrev 初始值为 nullptr

// 思路一、反转指针classSolution{public: ListNode*reverseList(ListNode* head){ ListNode* curNode = head,*curPrev =nullptr;while(curNode){// 在 while 循环内保存 curNext，保证了 curNode 一定不为空，避免了对空指针解引用// 可以保证一定可以取到 curNext ，为空或非空 ListNode* curNext = curNode->next; curNode->next = curPrev; curPrev = curNode; curNode = curNext;}return curPrev;}};

• 思路二已经足够简洁正确，无需优化

以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步

分享到此结束啦
一键三连，好运连连！你的每一次互动，都是对作者最大的鼓励！征程尚未结束，让我们在广阔的世界里继续前行！ 🚀