单链表的环问题以及相交问题
程序员文章站
2022-06-06 13:39:37
...
1.求单链表是否有环?若有环,求环的入口点以及环的长度。
流程:创建一个有环的单链表——->
先判断是否有环:
public boolean isLoop(){
Entry fast = head;//走得快的结点
Entry slow = head;//走得慢的结点
while(fast != null && fast.next != null){
fast = fast.next.next;//快的两步走
slow = slow.next;//慢的一步走
if(fast == slow){//快的和慢的相遇则证明有环
return true;
}
}
return false;//否则没环
}
假若此时单链表有环,求环的入口点:
public int getEntryLoop(){
if(!isLoop()){//为保证稳定性,先判断是否有环
return -1;
}
Entry fast = head;
Entry slow = head;
//先找到相遇点
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
break;
}
}
slow = head;//找到相遇点之后使任意一个回到头结点位置
//使两个节点接着一步一步走直到相等,如图所示,两段距离均为x,此时的结点就是入口点
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return slow.data;
}
求环的长度:
public int getLengthLoop(){//看图可知环的长度就是相遇后的X加上相遇前的Y
int len = 0;
Entry fast = head;
Entry slow = head;
boolean tag = false;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow && tag == true){//第二次相遇
break;
}
if(fast == slow && tag == false){//第一次相遇
tag = true;
}
if(tag = true){
len++;
}
}
return len;
}
2.求两个单链表是否相交?若相交,求交点。
判断是否相交:
public boolean isCut(TestLink t1,TestLink t2){
TestLink.Entry head1 = t1.getHead();
TestLink.Entry head2 = t2.getHead();
int len1 = t1.getLength();
int len2 = t2.getLength();
int my_len = len1-len2;
if(my_len<0){//寻找最长的单链表,并且使head1指向最长的单链表
head1 = t2.getHead();
head2 = t1.getHead();
}
for(int i =0;i<my_len;i++){//使最长单链表走到和另外一个单链表同样的位置(如图的起跑线)
head1 = head1.next;
}
//然后同时一步一步走(如图从起跑线同时走)
while(head1 != null && head2 != null && head1 != head2){
head1 = head1.next;
head2 = head2.next;
}
//如果有某一处两个节点相同,则相交,否则不相交(寻找是否有如图的交点)
if(head1 == head2 && head1 != null && head2 != null){
return true;
}else{
return false;
}
}
求交点:
public int cutPoint(TestLink t1,TestLink t2){
TestLink.Entry head1 = t1.getHead();
TestLink.Entry head2 = t2.getHead();
int len1 = t1.getLength();
int len2 = t2.getLength();
int my_len = len1-len2;
if(my_len<0){//使head1指向最长的单链表
head1 = t2.getHead();
head2 = t1.getHead();
}
for(int i =0;i<my_len;i++){//使最长单链表走到和另外一个单链表同样的位置
head1 = head1.next;
}
//然后同时一步一步走
while(head1 != null && head2 != null && head1 != head2){
head1 = head1.next;
head2 = head2.next;
}
//如果有某一处两个节点相同,则相交,则输出值就是交点的值
if(head1 == head2 && head1 != null && head2 != null){
return head1.data;
}else{
return -1;
}
}
求交点值只是在判断有相交之后加上输出就实现了!!!