镇江市建设工程安全监督站网站,做暧免费观看网站,青岛网站排名提升,新开传奇最大网站999 #x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;数据结构 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录链表OJ题(二)1. 链表… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接数据结构 长路漫漫浩浩万事皆有期待 文章目录链表OJ题(二)1. 链表的中间节点1.1 思路--两次遍历1.2 题目附加条件1.2.1 思路-快慢指针2.总结上一篇链表OJ题链接【链表OJ题(一)】移除链表元素
链表OJ题(二)
1. 链表的中间节点
链接876. 链表的中间结点
描述 给定一个头结点为 head 的非空单链表返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 示例1 输入[1,2,3,4,5] 输出此列表中的结点 3 (序列化形式[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意我们返回了一个 ListNode 类型的对象 ans这样 ans.val 3, ans.next.val 4, ans.next.next.val 5, 以及 ans.next.next.next NULL. 示例2: 输入[1,2,3,4,5,6] 输出此列表中的结点 4 (序列化形式[4,5,6]) 由于该列表有两个中间结点值分别为 3 和 4我们返回第二个结点。 提示 给定链表的结点数介于 1 和 100 之间。
1.1 思路–两次遍历
因为这道题目并没有时间复杂度的规定所以我们只需要先遍历一遍链表统计链表当中的结点个数然后再遍历一遍链表寻找中间位置的结点即可。
代码实现
struct ListNode {int val;struct ListNode *next;
};struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* cur head;//记录当前结点位置int count 0;//记录链表中结点的总数while (cur)//遍历的停止条件{count;//总数加一cur cur-next;//指针后移}int mid count / 2;//中间结点与第一个结点之间相差的结点数struct ListNode* midnode head;//记录中间结点的位置while (mid--)//从第一个结点开始指针后移mid个结点{midnode midnode-next;//指针后移}return midnode;//返回中间结点
}1.2 题目附加条件
我们可以明显知道上面这种思路的时间复杂度是O(n2)那么我们有没有办法在只遍历一遍链表的情况下找到中间结点的位置呢也就是要求代码的时间复杂度为O(n)
1.2.1 思路-快慢指针
既然我们要找的是中间位置的结点那么我们可以定义两个指针第一个指针指向当前遍历到的最后一个结点第二个指针时刻指向已经遍历过的结点的中间结点。如此进行下去因为第二个指针始终指向的是已经遍历过的结点的中间结点所以当链表遍历完后直接返回第二个指针即可。这就是所谓的“快慢指针”。
寻找规律 我们不妨定义两个指针名叫fastslow。 fast记录当前遍历到的最后一个结点。快指针 slow记录已经遍历过的结点的中间结点。慢指针
通过观察我们可以发现当slow指针走一步时fast指针走一步或是走两步都满足slow指针指向的是已经遍历过的结点的中间结点。也就是slow指针走一步fast指针最多可以走两步。
所以我们可以遍历链表当fast指针遍历到链表末尾时就立刻返回此时的slow指针即可。
注意因为fast指针一次是走两步所以当fast指针指向的内容为空或是fast指针指向的结点所指向的内容(fast-next)为空时均停止遍历链表。
这两种情况下停止遍历立刻返回slow指针。这样我们就在只遍历了一遍链表的情况下找到了中间结点的位置即时间复杂度为O(n)。
代码实现
struct ListNode {int val;struct ListNode *next;
};struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fast head;//快指针struct ListNode* slow head;//慢指针while (fastfast-next)//遍历继续的条件{slow slow-next;//慢指针一次走一步fast fast-next-next;//快指针一次走两步}return slow;//返回慢指针
}2.总结
今天我们通过两种思路分析并完成链表的中间节点这道链表OJ题目也学到了一个新的思路–快慢指针在之后的题目中将再次出现它的使用。希望我的文章和讲解能对大家提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
