【LeetCode】7 给定的链表返回环的入口节点

题目

对于一个给定的链表,返回环的入口节点,如果没有环,返回null

拓展:

你能给出不利用额外空间的解法么?

思路

  • 首先判断是否有环,有环时,返回相遇的节点,无环,返回null

  • 有环的情况下, 求链表的入环节点

​ fast再次从头出发,每次走一步,
​ slow从相遇点出发,每次走一步,
​ 再次相遇即为环入口点。

代码:

package linkedlist;
//nowcoder pass
public class Solution {
     
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
         
        ListNode meetNode = meetingNode(head);
        if (meetNode == null) {//说明无环
            return null;
        }
         
        ListNode fast = head;
        ListNode slow = meetNode;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
         
        return slow;
    }
     
    //寻找相遇节点,如果无环,返回null
    public ListNode meetingNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return slow;
            }
        }
        return null;
    }
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×