在面试高级和资深java工程师时，几乎百分百会涉及数据结构与算法问题，而快慢指针即考较算法，也问到来了数据 结构，是个，块面试题的熟客，那快慢指针计算未知长度的单链表的三等分点来举例。
首先给出单链表的结点的基础结构,
public class Node {
public String data; // 结点的数据域
public Node next; // 节点的指针域
public Node(){
}
public Node(String data) {
this.data = data;
}
}
然后给出单链表的基础结构,和基础添加结点的方法
public class LinkList {
private Node head; //头结点
//调用LinkList构造方法时初始化head
public LinkList() {
head = new Node();
}
public void addNode(Node node) {
Node temp = head;
// 遍历寻找追后一个结点
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}
}
快慢指针确定单链表的长度时，需要确定单链表中是否有环。
基本思路是如果有环，那么快指针一定会在环中追上慢指针，从而相遇。实现代码如下。
public Boolean hasCycle(LinkList linkList){
if(head == null) {
return false;
}
if(head.next == null){
return false;
}
Node fast = head.next.next;
Node low = head.next;
while (true){
if(fast == null || fast.next ==null){
return false;
}
//代表快针追上慢指针，有环
if(fast.data == low.data || fast.next == null){
return true;
}else {
fast = fast.next.next;
low = low.next;
}
}
}
在判定单链表结构中无环的情况下
可以利用一个三倍速的指针快速跑完结点，从而单倍速的指针指向的就是三等分的第一个等分点。
/**
* 快慢指针快速寻找三等分点（单链表无环三等分点）
* @param linkList
*/
public void getTriSelectorNode(LinkList linkList){
Node speed1 = linkList.head;//一倍数指针
Node speed3 = linkList.head;//三倍速指针
while (speed3.next != null){
if(speed3.next.next.next != null){
//三倍速结点存在下一轮则其他指针都按各自速度前进
speed3 = speed3.next.next.next;
speed1 = speed1.next;
}else if(speed3.next.next != null){
//三倍速结点,第，三个结点为空，第二个结点不为空 ,如长度为8的链，三倍数指针指到7，单倍数指针指向的是3，单倍数指针四舍五入加一位跳转
speed3 = speed3.next.next;
speed1 = speed1.next;
}else {
//三倍速结点,第，三个结点为空，第二个结点也为空 ,如长度为9的链，三倍数指针指到7，单倍数指针指向的是3,单倍数指针不需要跳转
speed3 = speed3.next;
speed1 = speed1;
}
}
System.out.println(speed1.data);
}
如果单链表中有环，可以分开计算环结点前的长度和的长度。计算方法将在代码中说明
public int getCycleTriSelectorNode (LinkList linkList){
Node speed1 = linkList.head;//一倍数指针
Node speed3 = linkList.head;//三倍速指针
while (true){
speed1 = speed1.next;
speed3 = speed3.next.next.next;
if(speed1.next.data .equals(speed3.next.data)){
//找到快慢指针
break;
}
}
//慢针走了s步，则快针走了3s，s = 环结点前的长度 + 环结点到碰撞点的步数，
// 3s = 环结点前的长度 + 环结点到碰撞点的步数 + n*环长度（n是快结点比慢节点多跑的圈数）
// 也就是环结点前的长度 = n*环长度 - 环结点到碰撞点的步数
// 也就是头结点和相遇结点分别设一指针，同步(单步)前进，则最后一定相遇在环入口结点p。
Node p = linkList.head;
Node speed1Temp = speed1;
int headlength = 0; // 环节点前的长度
while (p != speed1){
p = p.next;
speed1Temp = speed1Temp.next;
headlength++;
}
//快指针和慢指针从碰撞点开始继续往前走，再次碰撞时所用的操作数就是环的长度Length环
int cyclelength = 0; // 环的长度
while (true){
speed1 = speed1.next;
speed3 = speed3.next.next.next;
if(speed1.next.data .equals(speed3.next.data)){
//找到
break;
}
cyclelength++;
}
//计算三等分点
return (int)(headlength+cyclelength)/3;
}
最后将测试代码与类代码一并汇总，可以直接运行。
public class LinkList {
private Node head; //头结点
//调用LinkList构造方法时初始化head
public LinkList(){
head = new Node();
}
public void addNode(Node node){
Node temp = head;
// 遍历寻找追后一个结点
while (temp.next != null){
temp = temp.next;
}
temp.next = node;
}
/**
* 判定链表中是否有环
* @param linkList
* @return
*/
public Boolean hasCycle(LinkList linkList){
if(head == null) {
return false;
}
if(head.next == null){
return false;
}
Node fast = head.next.next;
Node low = head.next;
while (true){
if(fast == null || fast.next ==null){
return false;
}
//代表快针追上慢指针，有环
if(fast.data == low.data || fast.next == null){
return true;
}else {
fast = fast.next.next;
low = low.next;
}
}
}
/**
* 快慢指针快速寻找三等分点（单链表无环三等分点）
* @param linkList
*/
public void getTriSelectorNode(LinkList linkList){
Node speed1 = linkList.head;//一倍数指针
Node speed3 = linkList.head;//三倍速指针
while (speed3.next != null){
if(speed3.next.next.next != null){
//三倍速结点存在下一轮则其他指针都按各自速度前进
speed3 = speed3.next.next.next;
speed1 = speed1.next;
}else if(speed3.next.next != null){
//三倍速结点,第，三个结点为空，第二个结点不为空 ,如长度为8的链，三倍数指针指到7，单倍数指针指向的是3，单倍数指针四舍五入加一位跳转
speed3 = speed3.next.next;
speed1 = speed1.next;
}else {
//三倍速结点,第，三个结点为空，第二个结点也为空 ,如长度为9的链，三倍数指针指到7，单倍数指针指向的是3,单倍数指针不需要跳转
speed3 = speed3.next;
speed1 = speed1;
}
}
System.out.println(speed1.data);
}
/**
* 快慢指针快速寻找三等分点（单链表有环三等分点）
* @param linkList
*/
public int getCycleTriSelectorNode (LinkList linkList){
Node speed1 = linkList.head;//一倍数指针
Node speed3 = linkList.head;//三倍速指针
while (true){
speed1 = speed1.next;
speed3 = speed3.next.next.next;
if(speed1.next.data .equals(speed3.next.data)){
//找到快慢指针
break;
}
}
//慢针走了s步，则快针走了3s，s = 环结点前的长度 + 环结点到碰撞点的步数，
// 3s = 环结点前的长度 + 环结点到碰撞点的步数 + n*环长度（n是快结点比慢节点多跑的圈数）
// 也就是环结点前的长度 = n*环长度 - 环结点到碰撞点的步数
// 也就是头结点和相遇结点分别设一指针，同步(单步)前进，则最后一定相遇在环入口结点p。
Node p = linkList.head;
Node speed1Temp = speed1;
int headlength = 0; // 环节点前的长度
while (p != speed1){
p = p.next;
speed1Temp = speed1Temp.next;
headlength++;
}
//快指针和慢指针从碰撞点开始继续往前走，再次碰撞时所用的操作数就是环的长度Length环
int cyclelength = 0; // 环的长度
while (true){
speed1 = speed1.next;
speed3 = speed3.next.next.next;
if(speed1.next.data .equals(speed3.next.data)){
//找到
break;
}
cyclelength++;
}
//计算三等分点
return (int)(headlength+cyclelength)/3;
}
public static void main(String[] args) {
LinkList linkList = new LinkList();
for(int i = 1;i < 9; i++){
Node node = new Node("结点"+i);
linkList.addNode(node);
}
// 形成环
// linkList.head.next.next.next.next.next.next.next.next.next = linkList.head.next.next.next.next;
if(linkList.hasCycle(linkList)){
int triSelectorlength = linkList.getCycleTriSelectorNode(linkList);
System.out.println("链表中------------有环");
System.out.println("结点"+triSelectorlength);
}else {
System.out.println("链表中-------------无环");
linkList.getTriSelectorNode(linkList);
}
}
}
网友评论