剑指Offer 37题 两个链表的第一个公共节点 Java版

时间:2022-10-04 11:01:31
package test;

public class GetFirstCommonNode {

class ListNode{
public String key;
public ListNode next;
}

public ListNode findFirstCommonNode(ListNode headOne, ListNode headTwo){

if(headOne == null || headTwo == null){
return null;
}

int length1 = getListLength(headOne);
int length2 = getListLength(headTwo);

int lenghtdif = length1 - length2;

ListNode headLong = headOne;
ListNode headShort = headTwo;

if(length2 > length1){
headLong = headTwo;
headShort = headOne;
lenghtdif = length2 - length1;
}

for(int i=0; i<lenghtdif; ++i){
headLong = headLong.next;
}

while((headLong!=null)&&(headShort!=null)&&(headLong!=headShort)){
headLong = headLong.next;
headShort = headShort.next;
}

ListNode firstCommonNode = headLong;

return firstCommonNode;
}




public int getListLength(ListNode head){
int length = 0;
ListNode node = head;
while(node!=null){
++length;
node = node.next;
}
return length;
}


public static void main(String[] args) {
// TODO Auto-generated method stub
GetFirstCommonNode node = new GetFirstCommonNode();

ListNode a = node.new ListNode();
a.key = "a";
ListNode b = node.new ListNode();
b.key = "b";
ListNode e = node.new ListNode();
e.key = "e";
ListNode d = node.new ListNode();
d.key = "d";
ListNode f = node.new ListNode();
f.key = "f";
ListNode h = node.new ListNode();
h.key = "h";

f.next = d;
d.next = b;
b.next = a;
h.next = e;
e.next = b;
b.next = a;
ListNode node1 = node.findFirstCommonNode(f, h);
System.out.println(node1.key);


}

}