leetcode160：相交链表

题目链接

leetcode

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

// 链表结点的定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：链表 A, B 共享尾部 common
void connectTail(ListNode* listA, ListNode* listB, ListNode* common) {
    ListNode* tailA = listA;
    while (tailA->next) {
        tailA = tailA->next;
    }
    tailA->next = common;

    ListNode* tailB = listB;
    while (tailB->next) {
        tailB = tailB->next;
    }
    tailB->next = common;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        if (head->next != nullptr) cout << "-> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    哈希集合

    遍历链表 headA，并将链表 headA 中的每个结点加入哈希集合中。
    遍历链表 headB，对于遍历到的每个结点，判断该结点是否在哈希集合中：
        如果当前结点不在哈希集合中，则继续遍历下一个结点；
        如果当前结点在哈希集合中，则后面的结点都在哈希集合中。
    因此，在链表 headB 中遍历到的第一个在哈希集合中的结点就是两个链表相交的结点。

    时间复杂度：O(m+n)
        其中 m 和 n 是分别是链表 headA 和 headB 的长度。
        遍历两个链表各一次。
    空间复杂度：O(m)
        其中 m 是链表 headA 的长度。
        使用哈希集合存储链表 headA 中的全部结点。
*/
class Solution_0 {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> visited;

        ListNode* temp = headA;
        while (temp != nullptr) {
            visited.insert(temp);
            temp = temp->next;
        }

        temp = headB;
        while (temp != nullptr) {
            if (visited.count(temp)) {
                return temp;
            }
            temp = temp->next;
        }

        return nullptr;
    }
};

/*
    双指针

    1.两个指针分别从两个链表头部开始扫描，每次分别走一步；
    2.如果指针走到 null，则从另一个链表头部开始走；
    3.当两个指针相同时，
        如果指针不是 null，那么指针位置就是相遇点；
        如果指针是 null，那么两个链表不相交；

    时间复杂度：O(m+n)
        其中 m 和 n 是分别是链表 headA 和 headB 的长度。
        两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
    空间复杂度：O(1)
*/
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }

        ListNode *p1 = headA, *p2 = headB;
        while (p1 != p2) {
            // p1 = p1 == nullptr ? headB : p1->next;
            // p2 = p2 == nullptr ? headA : p2->next;

            if (p1 == nullptr) {
                p1 = headB;
            } else {
                p1 = p1->next;
            }
            if (p2 == nullptr) {
                p2 = headA;
            } else {
                p2 = p2->next;
            }
        }
        return p1;
    }
};

int main() {
    Solution solution;
    // 测试用例：有相交节点
    vector<int> listA_nums = {4, 1};
    vector<int> listB_nums = {5, 6, 1};
    vector<int> common_nums = {8, 4, 5};

    // 创建链表
    ListNode* listA = createList(listA_nums);
    ListNode* listB = createList(listB_nums);
    ListNode* common = createList(common_nums);
    // 链表设置相交结点
    connectTail(listA, listB, common);

    cout << "Input: " << endl;
    printList(listA);
    printList(listB);
    cout << "Output: " << endl;
    ListNode* result = solution.getIntersectionNode(listA, listB);
    if (result) {
        cout << "Intersected value: " << result->val << endl;
    } else {
        cout << "No intersection" << endl;
    }

    // 释放内存
    // common 节点被两个链表共享，只需删除一次
    // deleteList(listA);
    // deleteList(listB);

    return 0;
}