数据结构--链表刷题(一)快慢指针（上）
https://developer.aliyun.com/article/1480781?spm=a2c6h.13148508.setting.14.5f4e4f0eUFaP8y
2.判断是否带环
https://leetcode.cn/problems/linked-list-cycle/description/
代码实现：
1.快慢指针
public class Solution { public boolean hasCycle(ListNode head) { if(head == null || head.next == null) return false; ListNode fast = head; ListNode slow = head; // 只要有环 则fast和slow一定会相遇 while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(fast == slow) return true; } return false; } }
2.使用哈希表
public class Solution { public boolean hasCycle(ListNode head) { Set<ListNode> seen = new HashSet<ListNode>(); while(head != null) { if(!seen.add(head)) { return true; } head = head.next; } return false; } }
2.环形链表的进阶
https://leetcode.cn/problems/linked-list-cycle-ii/submissions/
代码实现：
1.哈希表的实现 public class Solution { public ListNode detectCycle(ListNode head) { ListNode cur = head; Set<ListNode> seen = new HashSet<>(); while(cur != null) { // 如果包含 则证明走到了入口点 if(seen.contains(cur)) { return cur; }else { seen.add(cur); } cur = cur.next; } return null; } } 2.双指针 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) break; } // 跳出循环有两种condition if(fast == null || fast.next == null) return null; // fast = head 两个指针一起走 直到相同 fast = head; while(fast != slow) { fast = fast.next; slow = slow.next; } return slow; } }
