剑指offer-第五章优化时间和空间效率（两个链表的第一个公共节点）

思路1：要求的是两个链表的第一个公共节点，首先想到的是用栈来存放两个链表，然后依次从栈中抛出，直到最后一个相同的节点为止。但是要用到两个栈，空间复杂度为O（n）；

思路2：从头到尾分别遍历两个链表得到链表的长度风别为，len1和len2，求出两者的差值dif,然后现在长的链表上面走dif步，然后同步走剩下的节点，当就可以找到第一个公共节点了。

    public ListNode findFirstCommonNode(ListNode pHead1,ListNode pHead2){

        if(pHead1==null||pHead2==null)

            return null;

        int len1=0,len2=0;

        ListNode p1=pHead1,p2=pHead2;

        while(p1!=null){//获取第一个链表的长度

            len1++;

            p1=p1.m_pNext;

        }

        while(p2!=null){//获取第二个链表的长度

            len2++;

            p2=p2.m_pNext;

        }

        int dif=len1-len2;

        ListNode longList=pHead1;//定义较长的链表

        ListNode shortList=pHead2;//定义较短的链表

        if(dif<0){

            longList=pHead2;

            shortList=pHead1;

            dif=len2-len1;

        }

        for(int i=0;i<dif;i++)

            longList=longList.m_pNext;//让较长的链表遍历差长的部分

        while(longList!=null&&shortList!=null&&

            longList!=shortList){//同时遍历两个链表，当遍历到同一个节点时，遍历停止。

                longList=longList.m_pNext;

                shortList=shortList.m_pNext;

            }

        ListNode firstCommonNode=longList;

        return firstCommonNode;

    }