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;}
}
运行结果