面试题52(剑指offer)--两个链表的第一个公共结点

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

解法一：

    //计算两个链表的长度，长的链表先走比短的链表多的几步，然后两个链表再同时移动，直至节点相等或者为空
    public ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int countOne = getLinkNodeLength(pHead1);
        int countTwo = getLinkNodeLength(pHead2);
        int fontStep=countOne-countTwo;
        if (fontStep>=0){
            for (int i = 0; i < fontStep; i++) {
                pHead1 = pHead1.next;
            }
        }else {
            for (int j = 0; j < -fontStep; j++) {
                pHead2 = pHead2.next;
            }
        }
        while (pHead1 != pHead2) {
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return pHead1;
    }
    //计算链表的长度
    private static int getLinkNodeLength(ListNode node) {
        int linkNodeLen = 0;
        while (node != null) {
            linkNodeLen++;
            node = node.next;
        }
        return linkNodeLen;
    }

解法二：

  /**
     * 假如用a+c表示链表A,b+c表示链表B，即c为两个链表的公共部分，因为a+c+b必然与b+c+a相
     * 等，将当访问链表 A 的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；
     * 同样地，当访问链表 B 的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表
     * A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
     * @param pHead1 
     * @param pHead2
     * @return 
     */
    public ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1, l2 = pHead2;
        while (l1 != l2) {
            l1 = (l1 == null) ? pHead2 : l1.next;
            l2 = (l2 == null) ? pHead1 : l2.next;
        }
        return l1;
    }