【LeetCode】141. 环形链表 进阶题142. 环形链表 II

 141. 环形链表

这道题还是用经典的快慢指针法来做。每次让快的指针走两步，慢的走一步。如果有环，则绝对会在环内的某一节点相遇。思想跟物理知识有点关系，如果有环，则在相对运动过程中，可以相当于慢指针静止，快指针每次走一步，那么最终肯定会相遇。这也是判断有环的条件。

若无环，则快指针在走的过程中，最后肯定会为null。这是判断无环的条件。

 算法代码

public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast!=null&&fast.next!=null) {fast = fast.next.next;slow = slow.next;if(fast == slow) {return true;}}return false;}
}

运行结果

 

142. 环形链表 II

相比上一题，上个题只需要判断有环无环，此题在上个题的基础上还要返回链表开始入环的第一个节点。如果链表无环，则返回null。

思路就是当确定是有环的时候，再加入一个指向头结点的指针，此时让指向相遇点的指针和新加入的（指向头结点）的这两个指针，继续往后以相同“速度”往后走，直到“相遇”（指向同一个节点），此时所指的这个节点就是链表开始入环的第一个节点。

 算法代码

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast!=null && fast.next!=null){fast = fast.next.next;slow = slow.next;if(fast == slow) {ListNode node = head;  //新加入一个指向头结点的指针while(node != slow) {node = node.next;slow = slow.next;}return node; //返回slow也行}}return null;}
}

运行结果