-
分析:如果链表存在环,则遍历的时候永远会在这个环打转,如果不存在环则遍历到最后一个节点的下一个节点就是空的了,即是null。所以如果要判断一个链表是否存在环,则使用两个指针来遍历,一个慢指针一次走一格,一个快指针一次走两格,故如果存在环则在快的肯定会在环上撞见慢的,就跟人走路一样。具体实现如下:
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } // 同一起点准备出发 ListNode slowNode = head; ListNode fastNode = head; while (slowNode != null && fastNode != null) { // 慢的一次走一格 slowNode = slowNode.next; // 快的一次走两格 fastNode = fastNode.next; if (fastNode != null && fastNode.next != null) { fastNode = fastNode.next; } else { return false; } // 相遇: // 慢的一次走一步,快的一次走两步,故如果不存在环, // 则快的永远最先达到终点,期间不会与慢的相遇, // 如果相遇了则肯定有环 if (fastNode != null && slowNode != null && fastNode==slowNode) { return true; } } return false; } }
本文标题:leetcode 141. 环形链表(链表是否有环)
本文链接:https://blog.quwenai.cn/post/3264.html
版权声明:本文不使用任何协议授权,您可以任何形式自由转载或使用。







还没有评论,来说两句吧...