两个链表的第一个公共节点

时间:2022-04-15 21:47:49
package Link; 
/**
* @author wangpei
* @version
*创建时间:2017年3月24日 上午1:22:33
* 求两个链表的第一个公共子节点
* 对于链表1:a->b->c->n->p 2:v->k->n->p
* 第一个公共子节点就是两个链表第一次相交的点 n
* 思路:1.求链表1,2的长度len1,len2
* 2.对于长的链表,移动正数(len1-len2)位
* 3.同步比较链表1,2,求出相等的数值。
*/

public class FirstNodeOfPublic {
public static void main(String[] args) {
Linknode node1=new Linknode('a');
node1.next=new Linknode('b');
node1.next.next=new Linknode('c');
node1.next.next.next=new Linknode('n');
node1.next.next.next.next=new Linknode('p');
Linknode node2=new Linknode('v');
node2.next=new Linknode('k');
node2.next.next=new Linknode('n');
node2.next.next.next=new Linknode('p');
int length1=1;
int length2=1;
Linknode yu1=node1;
Linknode yu2=node2;
while(yu1.next!=null){//求链表1的长度
length1++;
yu1=yu1.next;
}

while(yu2.next!=null){//求链表2的长度
length2++;
yu2=yu2.next;
}
int move=0;
if(length1>length2) {//对于长的链表进行移位
move=length1-length2;
for(int i=0;i<move;i++)
node1=node1.next;
}
else {
move=length2-length1;
for(int i=0;i<move;i++)
node1=node1.next;
}
System.out.println(getFirstNodeOfPublic(node1,node2).val);//输出第一个公共节点的值

}
public static Linknode getFirstNodeOfPublic(Linknode node1,Linknode node2){
if(node1.val==node2.val){
return node1;
}
if(node1==null||node2==null) return null;
return getFirstNodeOfPublic(node1.next,node2.next);



}

}

class Linknode{
Linknode next;
char val;
public Linknode(char val){
this.val=val;

}

}