单链表的公共结点问题

声明： 本总结仅为个人学习总结，以防止遗忘而作，不得转载和商用。
题目:给定两个单向链表,计算两个链表的第一个公共结点,若没有公共节点,返回空
令两链表的长度为m,n,不妨认为m>=n,由于两个链表从第一个公共结点到链表的尾结点是完全重合的.所以前面的(m-n)个结点一定没有公共结点
算法:先分别遍历两个链表得到它们的长度m,n.长链表空转(m-n)次,同步遍历两链表,直至找到相同结点或到链表结束
时间复杂度O(m+n)
Java版本实现:

public static Node findFirstSameNode(Node pA, Node pB){
        //因为有头指针,所以指向第一个有效结点
        pA = pA.next;
        pB = pB.next;
        //计算两个链表的长度
        int nA = calcLength(pA);
        int nB = calcLength(pB);
        if (nA > nB) {//保证后面nB-nA > 0
            Node tempNode = pA;
            pA = pB;
            pB = tempNode;
            
            int temp = nA;
            nA = nB;
            nB = temp;
        }
        //空转nB-nA次
        for(int i=0;i<nB-nA;i++){
            pB = pB.next;
        }
        //齐头并进
        while(pA != null){
            if (pA.value == pB.value) {
                return pA;
            }
            pA = pA.next;
            pB = pB.next;
        }
        return null;
    }

测试代码：

        int pAData[] = {10,34,68,98,20,8,7,6};
        Node pA = new Node(0);
        for(int i=pAData.length-1;i>=0;i--){
            Node node = new Node(pAData[i]);
            node.next = pA.next;
            pA.next = node;
        }
        printLinkedList(pA);
        
        int pBData[] = {21,5,8,7,6};
        Node pB = new Node(0);
        for (int i = pBData.length-1; i>=0;i--) {
            Node node = new Node(pBData[i]);
            node.next = pB.next;
            pB.next = node;
        }
        printLinkedList(pB);
        Node findNode = findFirstSameNode(pA, pB);
        printLinkedList(findNode);

返回结果：
Linked List: 0->10->34->68->98->20->8->7->6->
Linked List: 0->21->5->8->7->6->
Linked List: 8->7->6->