链表

环形链表问题

思路来源

一周刷爆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;
      }