网站怎么做支付系统,汕头seo优化,怎么做自己网站,北京市建设官方网站141. 环形链表 这道题还是用经典的快慢指针法来做。每次让快的指针走两步#xff0c;慢的走一步。如果有环#xff0c;则绝对会在环内的某一节点相遇。思想跟物理知识有点关系#xff0c;如果有环#xff0c;则在相对运动过程中#xff0c;可以相当于慢指针静止#xff0… 141. 环形链表 这道题还是用经典的快慢指针法来做。每次让快的指针走两步慢的走一步。如果有环则绝对会在环内的某一节点相遇。思想跟物理知识有点关系如果有环则在相对运动过程中可以相当于慢指针静止快指针每次走一步那么最终肯定会相遇。这也是判断有环的条件。 若无环则快指针在走的过程中最后肯定会为null。这是判断无环的条件。 算法代码
public class Solution {public boolean hasCycle(ListNode head) {ListNode fast head;ListNode slow head;while(fast!nullfast.next!null) {fast fast.next.next;slow slow.next;if(fast slow) {return true;}}return false;}
}
运行结果 142. 环形链表 II
相比上一题上个题只需要判断有环无环此题在上个题的基础上还要返回链表开始入环的第一个节点。如果链表无环则返回null。 思路就是当确定是有环的时候再加入一个指向头结点的指针此时让指向相遇点的指针和新加入的指向头结点的这两个指针继续往后以相同“速度”往后走直到“相遇”指向同一个节点此时所指的这个节点就是链表开始入环的第一个节点。 算法代码
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast head;ListNode slow head;while(fast!null fast.next!null){fast fast.next.next;slow slow.next;if(fast slow) {ListNode node head; //新加入一个指向头结点的指针while(node ! slow) {node node.next;slow slow.next;}return node; //返回slow也行}}return null;}
}
运行结果
