public class FindCrossNode {
public static class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
}
public static Node findNode(Node head1, Node head2) {
if(head1 == null || head2 == null) {
return null;
}
Node p1 = head1;
Node p2 = head2;
int len1 = 0;
int len2 = 0;
int diff = 0;
//遍历链表1
System.out.println("单向链表1:");
while (p1.next != null) {
System.out.print(p1.data + "->");
p1 = p1.next;
len1++;
}
len1++;
System.out.println(p1.data);
System.out.println("链表1长度:" + len1);
//遍历链表2
System.out.println("单向链表2:");
while (p2.next != null) {
System.out.print(p2.data + "->");
p2 = p2.next;
len2++;
}
len2++;
System.out.println(p2.data);
System.out.println("链表2长度:" + len2);
//两个链表尾节点不相等,代表两个链表没有合并
if(p1 != p2) {
return null;
}
//找到两个链表的合并节点,并返回合并节点
diff = Math.abs(len1-len2);
p1 = (len1 > len2)?head1:head2;
p2 = (len1 > len2)?head2:head1;
for (int i=0; i<diff; i++) {
p1 = p1.next;
}
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
public static void main(String[] args) {
//初始化节点
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);
Node node8 = new Node(8);
Node node9 = new Node(9);
Node node10 = new Node(10);
//构建链表
node1.next = node2;
node2.next = node3;
node3.next = node8;
node4.next = node5;
node5.next = node6;
node6.next = node7;
node7.next = node8;
node8.next = node9;
node9.next = node10;
//找到合并节点
Node node = findNode(node1, node4);
System.out.println("合并节点元素值为:"+node.data);
}
}
评论