1. 环形链表的判定
-
问题描述
给定一个单链表，判断链表中是否存在环。 -
解题思路
设定两个指针：快指针_fast与慢指针_slow。 二者从链表头节点同时开始向后移动，快指针每次移动2步，即_fast = _fast.next.next；慢指针每次移动1步，即_slow = _slow.next。
若链表中存在环，那么在经过若干步后，二者一定能够相遇；否则，快指针_fast则会到达NULL。
并且，由于在每一步中，_fast指针都会比慢指针_slow多走一步，所以在二者相遇的时刻，慢指针一定还没有走完这个环。class Node{ int val; Node next; } public boolean isCyclic(Node head){ if(head==null) return false; Node fast = head, slow = head; while(slow!=null && fast!=null && fast.next!=null){ fast = fast.next.next; slow = slow.next; if(slow == fast) return true; } return false; }
2. 环形链表的环入口
-
问题描述
给定一个有环单链表，找到该有环链表的入环节点。 -
解题思路
在 1 的基础上，我们知道在二者相遇时_slow还没有走完链表。设两个指针的相遇点距离入环点的距离为x，链表起点距离入环点的距离为a，链表的总长度为L，环的长度为r，则有
- 慢指针走的距离： a + x
- 快指针走的距离： a + x + n*r (n为快指针多走的圈数)
- 由于慢指针每走一步，快指针走两步，故有： 2 * (a + x) = a + x + n * r
所以： a + x = n * r- 我们对这个式子进行转换一下， 有： a = (r-x) + (n-1) * r
那么，这个式子说明了什么呢？很明显，等号左侧是从链表起点到入环节点的距离；对于等号右边，前一项(r-x) 表示的是从快慢指针相遇的位置到下一次来到入环节点的距离，后一项表示若干个环的距离。由此我们就得到了这个问题的答案：
当快慢指针相遇时，我们使用两个指针分别指向链表的头节点和相遇节点，然后二者同时移动，每次移动一步，那么下一次二者相遇的节点就是入环节点。
class Node{
int val;
Node next;
}
public boolean cyclicEntrance(Node head){
if(head==null) return null;
Node fast = head, slow = head;
Node p2 = null;
while(slow != null && fast!=null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(slow == fast){
p2 = slow;
break;
}
}
Node p1 = head;
while(p1 !=null && p2 != null){
if(p1 == p2) return p1;
p1 = p1.next;
p2 = p2.next;
}
}
3. 求解环上的节点数目
-
问题描述
给定一个有环单链表，求解环上的节点数目。 -
解题思路
- 思路 1
从 1 中快慢指针的相遇节点开始，继续让快慢指针向前走，那么下一次相遇时，快指针一定比慢指针多走了一个环的距离。
- 思路 2
根据 2 中的入环节点，从它出发，下次在来到这个节点，那么就是走了一个环的距离。
class Node{ int val; Node next; } public boolean cyclicLenght(Node head){ if(head==null) return 0; Node fast = head, slow = head; while(slow != null && fast!=null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(slow == fast) break; } int counter = 0; while(true){ slow = slow.next; fast = fast.next.next; counter += 1; if(slow == fast) return counter; } }
4. 两个链表是否相交(拓展题)
-
问题描述
给定两个单链表 A 和 B，判断二者是否相交。
-
解题思路
对于这个问题，我们可以分三种情况讨论：
- 两个链表中均没有环；
- 两个链表中其中一个有环；
- 两个链表中均有环。
对于情况1，除了采用Hash的方法，我们还可以采用两种更优雅的方式。
(1) 我们可以将 A 的尾节点指向 B 的头节点，这样假设A 和 B存在交点，那么在这个链表中一定会存在一个环。这样就将这个题目转化为判断一个链表是否有环的问题，方法见1. 环形链表的判定。
(2) 假设两个链表存在交点，那么二者的尾节点一定是相同的。那么我们只需要将两个链表均找到其尾节点，判断是否相同即可。对于情况2，如果 A 和 B 中只有一个存在环，那么二者不可能存在相交的情况。假设A中有环，B中无环，而且A和B相交。那么不论交点在入环之前，还是在环上，B 都会到达A中的环，从而B中也会存在环，与假设矛盾。
对于情况3，我们也可以采用两种不同的方式。
(1) 找到 A 的入环点，将其断开，变成一个无环链表。这时候再去判断 B 是否同样变为无环链表。若是，则 A 和 B 相交，否则 A 和 B 不相交。
(2) 同时找到 A 和 B 的入环点，判断是否相同，若相同，则 A 和 B 相交。如果不同，则从 B 的入环点开始对环进行遍历，若找到一个节点与 A 的入环点相同，那么二者相交，否则不相交。class Node{ int val; Node next; } public boolean isIntersectant(Node head_a， Node head_b){ if(head_a==null || head_b==null) return false; // 判断 A 是否存在环 boolean cyclic_a = isCyclic(head_a); // 判断 B 是否存在环 Node slow = head_b, fast = head_b; Node slow_pre = null; // 用来记录slow之前的一个节点，在进行环路断开时使用 boolean cyclic_b = false; while(slow != null && fast.next != null){ fast = fast.next.next; pre_slow = slow; slow = slow.next; if(slow == fast) cyclic_b = true; } if(cyclic_a^cyclic_b) return false; //二者相异则返回false if(cyclic_b){ // 二者都有环 // 找到b的入环点 Node p_b = head_b; while(p_b!=null && slow!=null){ if(p_b == slow) break; p_b = p_b.next; slow_pre = slow; slow = slow.next; } slow_pre.next = null; // b 环路断开 if(isCyclic(head_a)) return false; // b环路断开后，a仍然有环，则不相交 else return true; }else{ // 二者均无环 Node p_a = head_a, p_b = head_b; while(p_a.next != null) p_a = p_a.next; // a的尾节点 while(p_b.next != null) p_b = p_b.next; // b的尾节点 if(p_a == p_b) return true; else return false; } }
