快慢指针
所谓快慢指针:就是利用两个指针移动速度的不同来实现需求,一般设置两个指针,慢指针每次移动一格,快指针每次移动两格。下面分享利用快慢指针解决中间值、链表环路以及环路入口的问题。
中间值问题
利用快慢指针,当快指针移动到尾部的时候,慢指针所在的位置即为链表的中间位置
public class FastSlow {
public static void main(String[] args) {
Node<String> first = new Node<String>("aa", null);
Node<String> second = new Node<String>("bb", null);
Node<String> third = new Node<String>("cc", null);
Node<String> fourth = new Node<String>("dd", null);
Node<String> fifth = new Node<String>("ee", null);
Node<String> six = new Node<String>("ff", null);
Node<String> seven = new Node<String>("gg", null);
Node<String> eight = new Node<String>("hh", null);
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
fifth.next = six;
six.next = seven;
seven.next = eight;
System.out.println("中间值是:"+getMid(first));
}
public static String getMid(Node head){
Node<String> fast = head;
Node<String> slow = head;
while (fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
return slow.item;
}
}
单向链表有环问题
原理:因为快指针始终走比慢指针快,那么如果有环,则一定会相遇,即如果快慢指针指向了同一个节点,证明有环
public class CircleCheck {
public static void main(String[] args) {
Node<String> first = new Node<String>("aa", null);
Node<String> second = new Node<String>("bb", null);
Node<String> third = new Node<String>("cc", null);
Node<String> fourth = new Node<String>("dd", null);
Node<String> fifth = new Node<String>("ee", null);
Node<String> six = new Node<String>("ff", null);
Node<String> seven = new Node<String>("gg", null);
Node<String> eight = new Node<String>("hh", null);
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
fifth.next = six;
six.next = seven;
seven.next = third;
System.out.println("链表是否有环:"+isCircle(first));
}
public static boolean isCircle(Node<String> head){
Node<String> fast = head;
Node<String> slow = head;
while (fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if (fast.equals(slow)){
return true;
}
}
return false;
}
}
有环链表入口问题
当快慢指针相遇时,我们可以判断到链表中有环,这时重新设定一个新指针指向链表的起点,且步长与慢指针一样为1,则慢指针与“新”指针相遇的地方就是环的入口
public class CircleCheck {
public static void main(String[] args) {
Node<String> first = new Node<String>("aa", null);
Node<String> second = new Node<String>("bb", null);
Node<String> third = new Node<String>("cc", null);
Node<String> fourth = new Node<String>("dd", null);
Node<String> fifth = new Node<String>("ee", null);
Node<String> six = new Node<String>("ff", null);
Node<String> seven = new Node<String>("gg", null);
Node<String> eight = new Node<String>("hh", null);
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
fifth.next = six;
six.next = seven;
seven.next = third;
System.out.println("链表环的入口为:"+getEntrance(first).item);
}
public static Node getEntrance(Node<String> head){
Node<String> fast = head;
Node<String> slow = head;
Node<String> temp = null;
while (fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if (fast.equals(slow)){
temp = head;
continue;
}
if (temp!=null){
temp = temp.next;
if (temp.equals(slow)){
break;
}
}
}
return temp;
}
}
参考
黑马程序员Java数据结构与java算法全套教程
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)