题目：

输入两个链表，找出它们的第一个公共结点。

链表的形式肯定如下图所示：

 

 

暴力解法的时间复杂度为O(mn)显然不是最优的。下面介绍两种解法：

第一种思路：从后面往前数，最后一个相同的结点就是第一个相同的结点。分别把两个链表的所有节点放到两个栈里面，比较弹出栈的元素最后一个相等的节点就是第一个相同的结点。

第二种思路：先计算两个链表的结点数，计算出两个链表相差的结点数，长的链表先走相差的数，然后一起走，找到第一个相同的结点就是所求结果。

参考代码：

package test;import java.util.Stack;class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}public class Solution {    /**     * 基于栈的解法，时间复杂度为O(m+n),空间复杂度为O(m+n)     * @param pHead1     * @param pHead2     * @return     */    public ListNode FindFirstCommonNodeStack(ListNode pHead1, ListNode pHead2) {        if (pHead1 == null || pHead2 == null) return null;        Stack
     
       stack1 = new Stack
      
       ();        Stack
       
         stack2 = new Stack
        
         ();        ListNode p1 = pHead1;        ListNode p2 = pHead2;        while (p1 != null){            stack1.add(p1);            p1 = p1.next;        }        while (p2 != null){            stack2.add(p2);            p2 = p2.next;        }        ListNode result = null;        while(!stack1.isEmpty() && !stack2.isEmpty()){            if (stack1.peek().val == stack2.peek().val){                stack1.pop();                result = stack2.pop();            }else{                return result;            }        }        return result;    }        /**     * 基于链表规律的解法，时间复杂度为O(m+n),空间复杂度为O(1)     * @param pHead1     * @param pHead2     * @return     */    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {        if (pHead1 == null || pHead2 == null) return null;        ListNode longList = pHead1;        ListNode shortList = pHead2;        int pHead1Len = getListLen(pHead1);        int pHead2Len = getListLen(pHead2);        int diff = pHead1Len - pHead2Len;        if (diff < 0){            longList = pHead2;            shortList = pHead1;            diff = pHead2Len - pHead1Len;        }        int longListCount = 0;        while (longList != null){            if (longListCount == diff){                break;            }            longList = longList.next;            longListCount ++;        }        while (longList != null && shortList != null){            if (longList.val == shortList.val){                return longList;            }            longList = longList.next;            shortList = shortList.next;        }        return null;    }    public int getListLen(ListNode pHead){        int count = 0;        while (pHead != null){            pHead = pHead.next;            count ++;        }        return count;    }        }