当前位置: 首页> 汽车> 行情 > 51软件测试网站_seo网上培训课程_广州seo网站公司_企业微信会话内容存档

51软件测试网站_seo网上培训课程_广州seo网站公司_企业微信会话内容存档

时间:2025/7/11 14:45:41来源:https://blog.csdn.net/ouyfg/article/details/146426998 浏览次数: 1次
51软件测试网站_seo网上培训课程_广州seo网站公司_企业微信会话内容存档

明明是道简单题,却是众多公司最爱考的题之一。所以要按题目里的进阶用迭代和递归的方式完成

题目:

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5]

输出:[5,4,3,2,1]

示例 2:

输入:head = [1,2]

输出:[2,1]

示例 3:

输入:head = [] 输出:[]

提示:

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

思路:

        基本思路其实就是遍历链表,在遍历过程中,将当前节点的 next 指针指向前一个节点,然后更新前一个节点和当前节点,继续遍历下一个节点,直到遍历完整个链表。重要的是写代码的方式。

代码实现:

(1)迭代 

class Solution {
public:ListNode* reverseList(ListNode* head) {// 这个指针将用于记录当前节点的前一个节点,在反转过程中会不断更新ListNode* prev = nullptr;// 这个指针将用于遍历链表,从链表的头节点开始ListNode* curr = head;//只要 curr 指针不为 nullptr,就表示链表还没有遍历完while (curr != nullptr) {// 因为在反转过程中,curr->next 会被修改,所以需要提前保存下一个节点的信息ListNode* nextNode = curr->next;// 将当前节点 curr 的 next 指针指向前一个节点 prevcurr->next = prev;// 更新 prev 指针,将其指向当前节点 currprev = curr;// 更新 curr 指针,将其指向下一个节点 nextNodecurr = nextNode;}return prev;}
};

复杂度分析

  • 时间复杂度:O(n),其中 n 是链表的长度。需要遍历链表一次。
  • 空间复杂度:O(1),只使用了常数级的额外空间。

(2) 递归

        对于反转链表而言,递归的核心在于假设链表从第 k+1 个节点开始的部分已经反转完成,那么只需将第 k 个节点正确接入反转后的部分,就能完成整个链表的反转。

class Solution {
public:ListNode* reverseList(ListNode* head) {// 递归终止条件:链表为空或只有一个节点,直接返回该节点if (head == nullptr || head->next == nullptr) {return head;}// 递归反转当前节点之后的链表ListNode* newHead = reverseList(head->next);// 将当前节点的下一个节点的 next 指针指向当前节点head->next->next = head;// 当前节点的 next 指针置为 nullptrhead->next = nullptr;return newHead;}
};

代码解释

  1. 递归终止条件:当链表为空或者只有一个节点时,不需要进行反转,直接返回该节点。
  2. 递归调用:递归调用 reverseList 函数来反转当前节点之后的链表,得到反转后的新头节点。
  3. 调整指针:将当前节点的下一个节点的 next 指针指向当前节点,同时将当前节点的 next 指针置为  nullptr
  4. 返回新头节点:返回反转后的新头节点

复杂度分析

  • 时间复杂度:O(n),这里的 n 是链表的长度。因为需要对链表中的每个节点进行一次递归操作。
  • 空间复杂度:O(n),主要是递归调用栈的空间开销,递归的深度最大为链表的长度 n。 
关键字:51软件测试网站_seo网上培训课程_广州seo网站公司_企业微信会话内容存档

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: