记录关于链表的面试题
判断单链表中是否有环？
- 直接遍历解法，每遍历一个元素都要和前面遍历过的所有元素进行比较，时间复杂度比较高为O(n^2)
//使用遍历校验看单链表是否有环，时间复杂度O(n^2) ,空间复杂度O(1)
public boolean checkIsRing() {
Node pre;
Node cur = head;
while (cur != null) {
pre = cur;
cur = cur.next;
Node compare = head;
while (compare != null && compare != pre) {
if (compare == cur) {
return true;
}
compare = compare.next;
}
}
return false;
}
- HashMap空间换时间解法
//使用HashMap保存历史链表，降低时间复杂度O(n) 空间复杂度变为O(n)
public boolean checkIsRingWithHashMap() {
HashMap<Node, Integer> store = new HashMap<>();
Node cur = head;
int count = 1;
while (cur != null) {
if (store.containsKey(cur)) {
return true;
}
store.put(cur, count++);
cur = cur.next;
}
return false;
}
- 快慢指针，采用追击问题的解决方式来操作。若有环则快指针会和慢指针相遇
//使用快慢指针 时间复杂度O(n) ,空间复杂度O(1)
public boolean checkIsRingWithQuickAndSlowNode() {
Node slow = head;
Node quick = head;
while (slow != null && quick != null) {
slow = slow.next;
quick = quick.next.next;
if (slow == quick) {
return true;
}
}
return false;
}
有环那么环的长度是多少？
该问题，统计两次相遇之间的遍历次数即可
//返回单链表的环长度
public int getRingLength() {
int cycle = 0;
int count = 0;
Node slow = head;
Node quick = head;
while (quick != null && quick.next != null) {
slow = slow.next;
quick = quick.next.next;
count++;
if (slow == quick) {
if (cycle == 1) {
return count;
}
cycle++;
count = 0;
}
}
return 0;
}
环的起始节点是什么？
这个问题不好想到关联关系，为了解释，引用<漫画算法>里面的一张图
判断环的起始节点
由图我们我们很简单的可以通过行走的距离得到
2(D+S1)=D+2S1+S2，从而得到一个重要结论，那就是D=S2，也就是头结点到入环节点的位置等于首次相遇到入环点的位置，那么我们只要在相遇的时候，将任一节点移动到头结点，然后快慢指针速度变为1即可，下面为实现源码
//获取入环节点
public Node getRingStartNode() {
Node slow = head;
Node quick = head;
while (quick != null && quick.next != null) {
slow = slow.next;
quick = quick.next.next;
if (slow == quick) {
//相遇了,让slow到头结点
slow = head;
break;
}
}
if (quick != null && quick.next != null) {
while (slow != quick) {
//修改快慢节点的速度
slow = slow.next;
quick = quick.next;
}
}
return slow;
}
