题目描述
输入两个链表，找出它们的第一个公共结点。下图中6为公共结点：
思路分析
如果两个链表有公共节点，那么公共节点出现在两个链表的尾部。如果我们从两个链表的尾部开始往前比较，那么最后一个相同的节点就是我们要找的节点。
- 解决这个问题:分别把两个链表的节点放入两个栈里，这样两个链表的尾节点就位于两个栈的栈顶，接下来比较两个栈顶的节点是否相同。如果相同，则把栈顶弹出接着比较下一个栈顶，直到找到最后一个相同的节点。
- 首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。在第二次遍历的时候，在较长的链表上先走若干步，接着同时在两个链表上遍历，找到的第一个相同的节点就是它们的第一个公共节点。
测试用例
- 功能测试：输入的两个链表有公共节点:第一个公共节点在链表的中间，第一个公共节点在链表的末尾，第一个公共节点是链表的头节点;输入的两个链表没有公共节点。
- 特殊输入测试：输入的链表头节点是nullptr指针。
Java代码
public class Offer052 {
public static void main(String[] args) {
test1();
test2();
test3();
}
public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
return Solution1(pHead1,pHead2);
}
/**
* 利用长度关系
* @param pHead1
* @param pHead2
* @return
*/
private static ListNode Solution1(ListNode pHead1, ListNode pHead2) {
int listLength1 = getListLength(pHead1);
int listLength2 = getListLength(pHead2);
int dif = listLength1-listLength2;
ListNode longList = pHead1;
ListNode shortList = pHead2;
if(listLength1<listLength2) {
longList = pHead2;
shortList = pHead1;
dif = listLength2-listLength1;
}
for(int i=0;i<dif;i++) {
longList = longList.next;
}
while(longList!=null && shortList!=null && longList!=shortList) {
longList = longList.next;
shortList = shortList.next;
}
ListNode firstCommonFirst = longList;
return firstCommonFirst;
}
private static int getListLength(ListNode pHead1) {
int length = 0;
while(pHead1!=null) {
length++;
pHead1 = pHead1.next;
}
return length;
}
private static void test1() {
}
private static void test2() {
}
private static void test3() {
}
}