ps可以做网站动态图,宁波设计公司有哪些,江小白网络营销案例分析,甘肃seo网站强大#xff0c;不动如山的强大#xff0c;不会输给自己的真正的强大。 往期回顾#xff1a;
数据结构——单链表
单链表力扣刷题
文章目录
经典例题#xff1a;链表的中间结点
题目分析及双指针思路引入
双指针图解
leetcode 核心代码
判断环形链表——快慢指针… 强大不动如山的强大不会输给自己的真正的强大。 往期回顾
数据结构——单链表
单链表力扣刷题
文章目录
经典例题链表的中间结点
题目分析及双指针思路引入
双指针图解
leetcode 核心代码
判断环形链表——快慢指针延伸为追及问题
题目分析图解
leetcode 核心代码 大家好我是纪宁。 数据结构链表部分的面试、笔试大多都是在单链表部分且大多题都是没有哨兵位的头结点题目相数组通常比较难。这篇文章就给大家介绍一个单链表这里做题的常用技巧——快慢指针。 所谓快慢指针就是有两个指针来维护单链表通常定义为 slow 和 fast 这两个指针遍历链表的速度不同。
经典例题链表的中间结点 给你单链表的头结点 head 请你找出并返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。 题目分析及双指针思路引入 在这个题中如果要找的是数组中间元素的话可能比较简单直接计算出数组大小再规定只遍历一半的内容即可。但是在链表你除了知道当前结点的内容和下一节点的地址一无所知所以不能控制指针走的位置。 有一个特别巧妙的方法就是定义两个指针一个指针 slow 每次向后走一步 slow slow-next一个指针每次向后走两步fast fast - next -next 这样当指针 fast 或者 fast- next 成为 NULL 指针的时候slow 指针恰好走到了链表中间的位置这样就找到了链表的中间结点。
双指针图解
当链表长度为奇数时 当链表长度为偶数时 leetcode 核心代码
struct ListNode* middleNode(struct ListNode* head){struct ListNode*slow,*fast;slowhead;fasthead;while(fast!NULLfast-next!NULL){fastfast-next-next;slowslow-next;}return slow;
} 代码中要注意的一点是因为fast 指针一次走‘两步’所以循环的终止条件是 fast 或者 fast- next 为空最后返回 slow 指针。
判断环形链表——快慢指针延伸为追及问题
题目给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。 题目分析图解 如图上面这个链表就是在 d3 进入环d6的指针域指向d3然后链表就会在 d3——d4——d5——d6——d3 这个环中循环。 首先这道题没有给出进入环的位置所以进环有很多种可能这就排除了遍历链表的想法。这道题也可以使用快慢指针的方法fast 指针和 slow 指针同时开始从头指针往后走fast指针每次走两步slow指针每次走1步看这两个指针能否相遇。 如果链表带环则快指针和慢指针一定会相遇否则就不会相遇。这个追击原理类似于和你女朋友一起去操场跑圈你们同时出发只要你跑的比她快并且你们在相遇前都不停就一定能实现套圈。 所以只要在指针 fast 和 指针 slow 往后走的时候发现他们的指向相同fastslow的时候就说明链表带环套圈了。如果fast 或 fast-next 为空说明链表遍历已经结束链表不带环。
leetcode 核心代码
bool hasCycle(struct ListNode *head) {struct ListNode *slowhead;struct ListNode *fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(fastslow)return true;}return false;
} 这就是博主给大家带来的单链表部分刷题的常用技巧——快慢指针感谢观看。
