两个链表间的公共节点

题目：

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

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

 

暴力解法的时间复杂度为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<ListNode> stack1 = new Stack<ListNode>();
        Stack<ListNode> stack2 = new Stack<ListNode>();
        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;
    }
    
    
}