C++ 解决求两个链表的第一个公共结点问题

下面我将为您详细讲解C++如何解决求两个链表的第一个公共结点问题。

问题描述

给定两个单向链表的头指针head1和head2，请找出它们的第一个公共结点。

解决思路

要想求两个链表的第一个公共结点，我们可以使用如下思路：

1. 先遍历两个链表得到它们的长度len1和len2。同时标记一下两个链表的尾节点是否相同。
2. 如果两个链表的尾节点不同，则两个链表没有公共节点，直接返回nullptr。
3. 如果两个链表的尾节点相同，则让长一点的链表的头指针先向后移动len1 - len2个节点。
4. 然后同时遍历两个链表，直到找到第一个公共节点，如果没有公共节点则返回nullptr。

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* FindFirstCommonNode(ListNode* head1, ListNode* head2) {
        if (!head1 || !head2) {  // 其中一个链表为空则直接返回
            return nullptr;
        }
        int len1 = getListLength(head1);
        int len2 = getListLength(head2);
        ListNode *pLong, *pShort;
        int diff;
        if (len1 > len2) {  // 长短链表分别指向
            pLong = head1;
            pShort = head2;
            diff = len1 - len2;
        } else {
            pLong = head2;
            pShort = head1;
            diff = len2 - len1;
        }
        while (diff--) {
            pLong = pLong -> next;
        }
        while (pLong && pShort && pLong != pShort) {
            pLong = pLong -> next;
            pShort = pShort -> next;
        }
        return pLong;
    }
private:
    int getListLength(ListNode* head) {
        int length = 0;
        ListNode* p = head;
        while (p) {
            ++length;
            p = p -> next;
        }
        return length;
    }
};

如上所示，我们首先判断两个链表中是否有一个为空，如果有一个为空则直接返回nullptr。然后遍历两个链表得到它们的长度，并且同时标记一下它们的尾节点是否相同。如果两个链表的尾节点不同，则直接返回nullptr。如果两个链表的尾节点相同，则让长一点的链表的头指针先向后移动len1 - len2个节点，然后同时遍历两个链表，直到找到第一个公共节点，如果没有公共节点则返回nullptr。

示例说明

示例1

链表1：1 -> 2 -> 3 -> 6 -> 7
链表2：4 -> 5 -> 6 -> 7

这两个链表的第一个公共节点是6。

ListNode* head1 = new ListNode(1);
head1 -> next = new ListNode(2);
head1 -> next -> next = new ListNode(3);
ListNode* p = head1 -> next -> next;
p -> next = new ListNode(6);
p -> next -> next = new ListNode(7);

ListNode* head2 = new ListNode(4);
head2 -> next = new ListNode(5);
p = head2 -> next;
p -> next = head1 -> next -> next -> next;

Solution sol;
ListNode* res = sol.FindFirstCommonNode(head1, head2);
cout << res -> val << endl;  // 输出 6

示例2

链表1：1 -> 2 -> 3
链表2：4 -> 5 -> 6 -> 7

这两个链表没有公共节点。

ListNode* head1 = new ListNode(1);
head1 -> next = new ListNode(2);
head1 -> next -> next = new ListNode(3);

ListNode* head2 = new ListNode(4);
head2 -> next = new ListNode(5);
ListNode* p = head2 -> next;
p -> next = new ListNode(6);
p = p -> next;
p -> next = new ListNode(7);

Solution sol;
ListNode* res = sol.FindFirstCommonNode(head1, head2);
cout << res << endl;  // 输出 nullptr

以上就是C++解决求两个链表的第一个公共结点问题的完整攻略，希望对您有所帮助！