链表

环形链表问题

思路来源

一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到

笔记内容

问题来源：基于力扣141题进行拓展
问题描述：

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回环开始点。否则，返回null 。
算法思路：
- 快慢指针
  
  快指针一次走两步，慢指针一次走一步。若快指针到达终点，链表无环；否则两个指针将相遇。当相遇情况出现，快指针回到链表开头，慢指针留在相遇结点。两个指针按照一次一步进行移动，当两个指针再次相遇，该结点为环开始点。
- 哈希表
  
  指针移动，查询当前结点是否已在哈希表中。没有则添加，有返回该环开始点。若指针为null，链表无环。

代码实现

//快慢指针
    public ListNode hasCycle(ListNode head) {
        if(head == null || head.next == null || head.next.next == null){
            return null;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while (slow != fast){
            if(fast.next == null || fast.next.next == null){return null;}
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = head;
        while (slow != fast){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

//哈希表
    public ListNode hasCycle1(ListNode head) {
        HashSet hashMap = new HashSet();
        while (head != null){
            if(hashMap.contains(head)){
                return head;
            }
            hashMap.add(head);
            head = head.next;
        }
        return null;
    }

526互联

环形链表问题

链表

环形链表问题

思路来源

笔记内容