剑指Offer——链表中环的入口结点

By AverageJoeWang
 标签:

链表中环的入口结点

  • 题目描述

  • 解题思路

    • 思路1

      • 之所以出现环,是因为在整个链表中出现了重复的节点,而遇到的第一个重复的节点就是环的入口节点。所以可以使用Set来保存遍历到的节点,因为Set集合是不允许出现重复元素的,所以当一个节点被第二次添加的时候,往Set中放元素是失败的。所以可以利用这一点找出第一个重复的元素。
    • 思路2

      • 如果链表存在环,那么计算出环的长度n,然后准备两个指针slow、fast,fast先走n步,然后slow和fase一块走,当两者相遇时,即为环的入口处
  • 代码实现

    • set实现

      /*
      public class ListNode {
      int val;
      ListNode next = null;
      
      ListNode(int val) {
        this.val = val;
      }
      }
      */
      import java.util.*;
      public class Solution {
      
      public ListNode EntryNodeOfLoop(ListNode pHead)
      {
        Set<ListNode> set = new HashSet<>();
        while (pHead != null && set.add(pHead)){
            pHead = pHead.next;
        }
        return pHead;
      }
      }
      
    • 2个指针实现

      /*
      public class ListNode {
      int val;
      ListNode next = null;
      
      ListNode(int val) {
        this.val = val;
      }
      }
      */
      public class Solution {
      
      public ListNode EntryNodeOfLoop(ListNode pHead)
      {
        if (pHead == null) return null;
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (fast.next != null)
        {
            fast = fast.next.next;
            if (fast == null) return null;
            slow = slow.next;
            if (slow == fast) break;
        }
        if (fast.next == null) return null;
        slow = pHead;
        while (slow != fast)
        {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
      }
      }