Java之单链表问题解决案例讲解

Java之单链表问题解决案例讲解

单链表

单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。

链表中的数据是以结点来表示的，每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

问题

问题1：给定一个单链表，判断链表中是vTQtIQfJdT否有环

问题2：给定一个链表，返回链表开始入环的第一个节点，如果无环，则返回null

class Node{

public int data;

http:// Node next;

public Node(int data){

this.data=data;

this.next=nvTQtIQfJdTull;

}

}

public class linkedList {

/*给定一个链表，判断链表中是否有环

思路： 如果链表有环的话，定义两个节点fast,slow。让fast一次走两步，slow一次走一步；

如果能相交，即fast=slow，说明有交点，且如果有环，节点的next也不会为空

*/

public Node head;

public boolean hasCycle(){

Node fast=this.head;

Node slow=this.head;

while (fast!=null&&fast.next!=null){//如果把fast.next写下前面，一旦fast为空，则会空指针异常

fast=fast.next.next;

slow=slow.next;

if(fast==slow){

return true;

}

}

return false;

}

//给定一个链表，返回链表开始入环的第一个节点，如果无环，则返回null

public Node detectCycle(){

/*定义fast与slow,fast前进2格，slow前进一格，如果有交点的话，fast与slow第一次相遇时，fast的路程为slow的2倍，

如设从头节点到入环节点的距离为X，令入环节点到fast,slow第一次相遇距离为Y，环的总长度为C的话;可得公式：2（X+Y）=X+Y+NC；

得X=NC-Y，令N等于1，X=C-Y;此时让slow从头节点开始走，当于速度相同的fast相遇时，则为入环的节点。

*/

Node fast=this.head;

Node slow=this.head;

while (fast!=null&&fast.next!=null){

fast=fast.next.next;

slow=slow.next;

if(fast==slow){//第一次相遇

break;

}

}

if(fast==null&&fast.next==null){

return null;

}

//此时让slow从头节点开始，与fast以相同速度前进，遇到则为入环的第一个节点

slow=this.head;

while (fast!=slow){

fast=fast.next;

slow=slow.next;

}

return slow;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。