赞
踩
当快慢指针相遇时,我们可以判断到链表中有环,这时重新设定一个新指针指向链表的起点,且步长与慢指针一样为1,则慢指针与“新”指针相遇的地方就是环的入口。证明这一结论牵涉到数论的知识,这里略,只讲实现。
这是一个哔哩哔哩老师错误的代码(bilibili里的2020JAVA基础-深入系统的学习数据结构与算法),我觉的逻辑是有一定的问题,会出现死循环。
什么情况呢?????
当有环链表出现足够长的没环的地方,此时就有可能出现死循环,当圆环节点数为3时,slow和fast相遇只需要3步,当前边足够长temp还没走到,他们又相遇了,temp又指向了first,所以这个逻辑肯定会出现死循环。错误代码如下。。。。。。
使用我的下边图像,使用上边的错误代码,老师的逻辑一定是错的(自己去画)
我画了一下正确代码的图像(根据我的代码逻辑)。
public class QuickSlowMid { //节点类 private static class Node<T> { T item; Node next; public Node(T item, Node next) { this.item = item; this.next = next; } } public static void main(String[] args) { Node<String> one = new Node<>("a", null); Node<String> two = new Node<>("b", null); Node<String> three = new Node<>("c", null); Node<String> four = new Node<>("d", null); Node<String> five = new Node<>("e", null); Node<String> six = new Node<>("f", null); Node<String> seven = new Node<>("g", null); one.next = two; two.next = three; three.next = four; four.next = five; five.next = six; six.next = seven; seven.next = five; Node entrance = getEntrance(one); System.out.println(entrance.item); } public static Node getEntrance(Node node) { Node fast = node; Node slow = node; Node temp = null; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { temp = node; continue; } if (temp != null) { temp = temp.next; if (temp == slow) { break; } } } return temp; }
正确的代码:
不满足这种状况(一个圆环)
满足所有有环情况。
public class QuickSlowMid { //节点类 private static class Node<T> { T item; Node next; public Node(T item, Node next) { this.item = item; this.next = next; } } public static void main(String[] args) { Node<String> one = new Node<>("a", null); Node<String> two = new Node<>("b", null); Node<String> three = new Node<>("c", null); Node<String> four = new Node<>("d", null); Node<String> five = new Node<>("e", null); Node<String> six = new Node<>("f", null); Node<String> seven = new Node<>("g", null); one.next = two; two.next = three; three.next = four; four.next = five; five.next = six; six.next = seven; seven.next = seven; Node entrance = getEntrance(one); System.out.println(entrance.item); } public static Node getEntrance(Node node) { Node fast = node; Node slow = node; Node temp = null; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { temp = node; while (true){ temp=temp.next; slow=slow.next; if (slow==temp){ return temp; } } } } return null; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。