每日一题 为了工作 2020 0329 第二十七题
/**
*
* 问题：
* 判断无环单链表相交问题
* 如何判断两个无环链表是否相交， 相交则返回第一个相交节点，不相交则返回 null。
* 如果两个无环链表相交， 那么从相交节点开始， 一直到两个链表终止的这一段， 是两个链
* 表共享的。
*
* 分析：
*1.链表 1从头节点开始，走到最后一个节点（不是结束），统计链表 1的长度记为 len1,同
*时记录链表 1的最后一个节点记为 end1。
*
*2.链表 2从头节点开始，走到最后一个节点（不是结束），统计链表2的长度记为 len2,同
*时记录链表 2的最后一个节点记为 end2。
*
*3.如果 end1 !=end2, 说明两个链表不相交， 返回 null即可；如果 end1=end2,说
*明两个链表相交， 进入步骤 4来找寻第一个相交节点。
*
*4.如果链表 1长，链表 1就先走 len1-len2步，如果链表2长，链表2就先走len2-len1
*步。然后两个链表一起走， 一起走的过程中， 两个链表第一次走到一起的那个节点， 就是第
*一个相交的节点。(因为相交之后节点元素共享，所以多出来的长度节点一定不可能相交)
*
*例如： 链表1长度为100, 链表2长度为30, 如果已经由步骤 3确定了链表 1和链表2一定相
*交， 那么接下来， 链表1先走70步， 然后链表 1和链表2一起走， 它们一定会共同进入第一个
*相交的节点。
*
* @author 雪瞳
*
*/
*代码
public class Node {
public int value;
public Node next;
public Node(int data){
this.value=data;
}
}
public class NodeLoop {
Node currentHead1 = null;
Node currentHead2 = null;
int lengthNode1=0;
int lengthNode2=0;
int len = 0;
public Node nodeLoop(Node head1,Node head2){
if(head1==null&&head2==null){
return null;
}
//遍历链表
currentHead1 = head1;
while(currentHead1!=null){
lengthNode1++;
currentHead1=currentHead1.next;
}
currentHead2 = head2;
while(currentHead2!=null){
lengthNode2++;
currentHead2=currentHead2.next;
}
//相交判断
if(currentHead1 !=currentHead2){
return null;
}else{
if(lengthNode1>lengthNode2){
int flag=0;
len=lengthNode1-lengthNode2;
currentHead1=head1;
currentHead2=head2;
while(currentHead1!=currentHead2){
if(flag==len){
currentHead1=currentHead1.next;
currentHead2=currentHead2.next;
}else{
currentHead1=currentHead1.next;
}
}
return currentHead2;
}else if(lengthNode1<lengthNode2){
int flag=0;
len=lengthNode2-lengthNode1;
currentHead1=head1;
currentHead2=head2;
while(currentHead1!=currentHead2){
if(flag==len){
currentHead1=currentHead1.next;
currentHead2=currentHead2.next;
}else{
currentHead2=currentHead2.next;
}
}
return currentHead1;
}else{
return head1;
}
}
}
}
import java.util.Random;
import java.util.Scanner;
public class TestNodeLoop {
public static void main(String[] args) {
NodeLoop loop = new NodeLoop();
TestNodeLoop test = new TestNodeLoop();
Scanner sc = new Scanner(System.in);
int length1;
System.out.println("请输入链表长度:...");
length1 = sc.nextInt();
int length2;
System.out.println("请输入链表长度:...");
length2 = sc.nextInt();
Node head1;
Node head2;
Node head3;
head1=test.getNodeList(length1);
head2=test.getNodeList(length2);
test.showByTip(head1);
test.showByTip(head2);
int loopLength;
System.out.println("请输入链表相交的节点位置:...");
loopLength = sc.nextInt();
head3=test.getLoopNode(head1,head2,loopLength);
test.showByTip(head3);
Node result = loop.nodeLoop(head2, head3);
if(result!=null){
System.out.println("链表相交相交元素如下:...");
test.showByTip(result);
}else{
System.out.println("链表没有相交");
}
sc.close();
}
//获得相交链表
private Node getLoopNode(Node head1, Node head2,int length) {
int flag=0;
Node current = null;
current =head1;
while(current!=null){
flag++;
if(flag==length){
current.next=head2;
return head1;
}
current=current.next;
}
System.out.println("链表不存在可以连接的位置，请增加元素...");
return null;
}
//显示
public void showByTip(Node head) {
Node current = null;
System.out.println("链表内的元素顺序显示如下：...");
current=head;
while(current!=null) {
System.out.print(current.value+" ");
current=current.next;
}
System.out.println("");
}
//生成链表
public Node getNodeList(int listLength) {
Random rand = new Random();
Node nodeList[]= new Node[listLength];
for(int i=0;i<listLength;i++) {
nodeList[i]= new Node(rand.nextInt(10));
}
for(int i=0;i<listLength-1;i++) {
nodeList[i].next=nodeList[i+1];
}
return nodeList[0];
}
}
*运行