快慢指针应用场景 - Java版

本文主要是介绍快慢指针应用场景 - Java版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 判断单向链表是不是一个环形链表

//判断是否有环，快指针走两步，满指针走一步，如果有环，两个指针会相遇public static boolean isRing(PointerBean root) {if (root == null) {return false;}PointerBean fast = root;PointerBean slow = root;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {return true;}}return false;}//找出环形节点public static PointerBean ring(PointerBean root) {if (root == null) {return null;}PointerBean fast = root;PointerBean slow = root;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {//有环,快指针留在原处，满指针回到头节点，然后各移动一次，相遇点就是环break;}}if (slow == fast) {slow = root;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow;}return null;}

2. 找两个链表的第一个公共节点

public static PointerBean publicNode(PointerBean root1, PointerBean root2) {if (root1 == null || root2 == null) {return null;}PointerBean p1 = root1;PointerBean p2 = root2;//定义两个指针p1 p2，分别指向两个链表的头节点，当其中一个(p1)指向尾部的时候，让p1指针，指向另一个链表的头部//当p2指向尾部的时候，让p2指向另一个链表的头部//当p1=p2的时候，就是公共节点while (p1 != p2) {p1 = p1 != null ? p1.next : root2;p2 = p2 != null ? p2.next : root1;}return p1;}

3. 找出单向链表倒数第k个节点

//倒数第k个节点，就是正数第(length - k)+1个节点//因此定义两个指针，让快指针先走k步，然后快慢指针同时开始走，当快指针走到尾部的时候，慢指针就是倒数第k个节点private static PointerBean inverse(PointerBean root, int inverse) {if (root == null) {return null;}PointerBean fast = root;PointerBean slow = root;int index = 0;while (fast != null) {fast = fast.next;if (index == inverse) {slow = slow.next;} else {index++;}}return slow;}

4. 找出单向链表的中间节点

//快指针是慢指针的2被速度即可private static PointerBean centerNode(PointerBean root) {if (root == null) {return null;}PointerBean fast = root;PointerBean slow = root;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}return slow;}

 

 

这篇关于快慢指针应用场景 - Java版的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---