剑指offer 两个链表的第一个公共结点

左手的ㄟ右手 2022-06-15 01:16 138阅读 0赞

# 1.题目描述 #

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

# 2.分析 #

如果两个链表有公共节点，那么这两条链表从该公共节点开始往后的部分是重合的。  
**方法1：**  
可以想象一个Y造型，前面分叉，后面从公共节点开始回合。  
步骤：  
1）求两个链表的长度差delta，较长的链表从head开始先走delta个节点  
2）两个链表从当前节点开始，依次比较节点是否相同。  
**方法2：**  
假设: 链表1分为两段 a+c，链表2分为两段b+c，其中c是两个链表的公共部分。  
同时开始遍历两个链表，当一个链表遍历到末尾之后就将它指向另一个链表的头部  
所以总共遍历的长度是：  
链表1 a+c+b+c  
链表2 b+c+a+c  
所以到最后肯定会相遇的。

# 3.代码 #

方法1：

class Solution {
    public:
        ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
            int len1 = 0;
            int len2 = 0;
            ListNode* temp = pHead1;
            while (temp) {
                ++len1;
                temp = temp->next;
            }
            temp = pHead2;
            while (temp) {
                ++len2;
                temp = temp->next;
            }
            int delta = abs(len1 - len2);//长度差
            //cout << len1 << " " << len2 << " " << delta << endl;
            if (len1 > len2) {
                while (delta) {
                    pHead1 = pHead1->next;
                    --delta;
                }
            }
            else {
                while (delta) {
                    pHead2 = pHead2->next;
                    --delta;
                }
            }
            while (pHead1 != NULL && pHead2 != NULL) {
                if (pHead1 == pHead2)
                    break;
                else {
                    pHead1 = pHead1->next;
                    pHead2 = pHead2->next;
                }
            }
            return pHead1;
        }
    };

方法2：

ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
        ListNode* p1 = pHead1;
        ListNode* p2 = pHead2;
        while (p1 != p2) {
            p1 = p1 == NULL ? pHead2 : p1->pNext;
            p2 = p2 == NULL ? pHead1 : p2->pNext;
        }
        return p1;
    }