题目：输入两个链表，找出它们的第一个公共结点。
代码如下：
package demo;
/**
* 两个链表的第1个公共结点
*
* @author xiangdonglee
*
*/
public class Test37 {
private static class ListNode {
int val;
ListNode next;
public ListNode() {
}
public ListNode(int val) {
this.val = val;
}
@Override
public String toString() {
return val + "";
}
}
public static ListNode findFirstCommonNode(ListNode head1, ListNode head2) {
// 得到2个链表的长度
int length1 = getListLength(head1);
int length2 = getListLength(head2);
int diff = length1 - length2;
ListNode longListHead = head1;
ListNode shortListHead = head2;
if (diff < 0) {
longListHead = head2;
shortListHead = head1;
diff = length2 - length1;
}
// 先在长链表上走几步，再同时在2个链表上遍历
for (int i = 0; i < diff; i++) {
longListHead = longListHead.next;
}
while (longListHead != null && shortListHead != null && longListHead != shortListHead) {
longListHead = longListHead.next;
shortListHead = shortListHead.next;
}
// 返回第一个公共结点，如果没有就返回null
return longListHead;
}
private static int getListLength(ListNode head) {
int result = 0;
while (head != null) {
result++;
head = head.next;
}
return result;
}
public static void main(String[] args) {
test1();
test2();
test3();
test4();
test5();
}
/**
* 第1个公共结点在链表中间
*/
private static void test1() {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
ListNode node6 = new ListNode(6);
ListNode node7 = new ListNode(7);
node1.next = node2;
node2.next = node3;
node3.next = node6;
node6.next = node7;
node4.next = node5;
node5.next = node6;
System.out.println(findFirstCommonNode(node1, node4));
}
/**
* 没有公共结点
*/
private static void test2() {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
ListNode node6 = new ListNode(6);
ListNode node7 = new ListNode(7);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node5.next = node6;
node6.next = node7;
System.out.println(findFirstCommonNode(node1, node5));
}
/**
* 公共结点是最后一个结点
*/
private static void test3() {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
ListNode node6 = new ListNode(6);
ListNode node7 = new ListNode(7);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node7;
node5.next = node6;
node6.next = node7;
System.out.println(findFirstCommonNode(node1, node5));
}
/**
* 公共结点是第一个结点，2个链表完全重合
*/
private static void test4() {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
ListNode node6 = new ListNode(6);
ListNode node7 = new ListNode(7);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node7;
System.out.println(findFirstCommonNode(node1, node1));
}
/**
* 输入的链表头结点是null指针
*/
private static void test5() {
System.out.println(findFirstCommonNode(null, null));
}
}
运行结果
test1()
test2()
test3()
test4()
