广西建设监理协会官方网站,网站建设的需求文档,网页编程html,域名链接网站作者简介#xff1a;大家好#xff0c;我是未央#xff1b; 博客首页#xff1a;未央.303 系列专栏#xff1a;牛客面试必刷TOP101 每日一句#xff1a;人的一生#xff0c;可以有所作为的时机只有一次#xff0c;那就是现在#xff01;#xff01;#xff01;… 作者简介大家好我是未央 博客首页未央.303 系列专栏牛客面试必刷TOP101 每日一句人的一生可以有所作为的时机只有一次那就是现在 文章目录
前言
一.反转链表
题目描述
解题分析 二.合并两个排序的链表
题目描述
解题分析
总结 前言
今天是我们第一天的牛客面试必刷TOP101比较简单一定要好好掌握清楚每天见 一.反转链表
题目描述 描述 给定一个单链表的头结点pHead(该头节点是有值的比如在下图它的val是1)长度为n反转该链表后返回新链表的表头。 数据范围 0≤10000≤n≤1000 要求空间复杂度O(1) 时间复杂度 O(n) 。 举例说明 如当输入链表{1,2,3}时 经反转后原链表变为{3,2,1}所以对应的输出为{3,2,1}。 以上转换过程如下图所示 示例1 示例2 解题分析 解题思路: 首先本题我们决定采用栈的方法来反转链表最为简单 因为栈是先进后出的。实现原理就是把链表节点一个个入栈当全部入栈完之后再一个个出栈出栈的时候在把出栈的结点串成一个新的链表 代码编写思路步骤 1.创建一个空栈和一个辅助指针current 并将current指向链表的头节点。 ⒉将节点逐个压入栈中直到链表的末尾。每次压入节点时将current 指针向后移动到下一个节点。 3.弹出栈中的节点并将其依次连接起来形成新的链表。 在这个过程中需要保持一个指针prev 用来指向新链表的头节点。 4.重复步骤3直到栈为空此时所有的节点都已经被反转。 5.将新链表的头节点返回作为结果。 复杂度分析 时间复杂度为O(n)其中n表示链表的长度。 空间复杂度是O(1)因为反转链表时只需要使用几个指针变量不需要额外的数据结构来存储节点。 图示说明: 代码编写 详细代码解析 步骤4中23~28行代码 while (!stack.isEmpty()) {ListNode node stack.pop();prev.next node;prev node;} 解析 在上述代码中prev.next node 的作用是将 prev 节点的 next 指针指向 node 节点即将当前节点与前一个节点进行连接。 首先我们将栈中弹出的第一个节点作为新链表的头节点将其赋给 newHead 变量。 接下来在循环中我们使用 prev 变量来表示当前的节点而 node 变量则表示从栈中弹出的下一个节点。于是prev.next node 表示将 prev 节点的 next 指针指向 node 节点将它们连接在一起。 然后通过 prev node 操作将 prev 更新为当前的节点 node以便在下一次循环中连接下一个节点。 通过这样的操作我们可以依次将栈中的节点连接起来最终形成反转后的链表。在循环结束后prev 指向的是新链表的尾节点。 二.合并两个排序的链表
题目描述 描述 输入两个递增的链表单个链表的长度为n合并这两个链表并使新链表中的节点仍然是递增排序的。 数据范围 0≤10000≤n≤1000−1000≤节点值≤1000−1000≤节点值≤1000 要求空间复杂度 O(1)时间复杂度 O(n)。 举例说明 如输入{1,3,5},{2,4,6}时合并后的链表为{1,2,3,4,5,6}所以对应的输出为{1,2,3,4,5,6}转换过程如下图所示 或输入{-1,2,4},{1,3,4}时合并后的链表为{-1,1,2,3,4,4}所以对应的输出为{-1,1,2,3,4,4}转换过程如下图所示 示例1 示例2 示例3 解题分析 解题思路 本题我们决定采用递归的方法解决比较简单方便 分类讨论 1.如果有一个链表为空返回另一个链表特殊情况 2.如果pHead1 节点值比小pHead2下一个节点应该是 pHead1应该return pHead1在return之前指定pHead1的下一个节点应该是pHead1.next和pHead2俩链表的合并后的头结点 3.如果pHead1 节点值比pHead2大下一个节点应该是pHead2应该return pHead2在return之前指定pHead2的下一个节点应该是pHead1和pHead2.next俩链表的合并后的头结点 代码编写思路步骤 1.首先编写一个递归函数用于合并两个排序链表。 2.在递归函数中判断某个链表是否为空。如果其中一个链表为空说明已经到达链表的末尾直接返回另一个链表。特殊情况 3.如果两个链表都不为空比较两个链表的头节点的值。将较小的头节点作为合并后链表的头节点。 4.然后递归地调用合并函数传入较小头节点的下一个节点和另一个链表。将递归返回的结果连接到较小头节点的后面形成合并后的链表。 5.最后返回合并后的链表作为结果。 复杂度分析 时间复杂度O(NM)M N分别表示pHead1, pHead2的长度 空间复杂度O(1)常数级空间 代码编写 总结
