问题1:输入两个链表,找出它们的第一个公共节点
问题2:将两个升序链表合成一个升序链表并返回,新链表是通过拼接给定的两个链表的所有节点组成的
/*输入两个链表,找出它们的第一个公共节点
如果两个链表的长度不一样,定义两个链表的头节点分别为pl(较长的链表),ps(较短的链表),
先计算两个链表的长度,得到的△,让较长的链表pl先走△个节点,与较短的链表ps长度相同时,
以同等速度向后走,当pl.next=ps.next,即为第一个公共节点
* */
public static Node getIntersectionNode(Node headA,Node headB){
int lenA=0;
int lenB=0;
Node pl=headA;
Node ps=headB;
while(pl!=null){
pl=pl.next;
lenA++;
}
while (ps!=null){
ps=ps.next;
lenB++;
}
int len=lenA-lenB;
if(len<0){
pl=headB;
ps=headA;
len=lenB-lenA;
}else{
pl=headA;
ps=headB;
}
for(int i=0;i<len;i++){
pl=pl.next;
}
while(pl!=ps&&pl!=null&&ps!=null){
ps=ps.next;
pl=pl.next;
}
if(pl==ps&&pl!=null&&ps!=null){
return pl;
}
return null;
}
/*将两个升序链表合成一个升序链表并返回,新链表是通过拼接给定的两个链表的所有节点组成的
定义了一个傀儡节点newHead来保存新链表第一个节点,tmp是从newHead开始,来收集新链表升序的引用,
可以把tmp看做“墙头草”,哪边小往哪边倒。
*/
public Node nergeTwolists(Node headA,Node headB){
Node newHead=new Node(-1);
Node tmp=newHead;
while (headA!=null&&headB!=null){
if(headA.data<headB.data){
tmp.next=headA;
headA=headA.next;
tmp=tmp.next;
}else {
tmp.next=headB;
headB=headB.next;
tmp=tmp.next;
}
}
if(headA!=null){
tmp.next=headA;
}
if(headB!=null){
tmp.next=headB;
}
return newHead.next;
}