力扣面试题 02.07. 链表相交

一 题目：

二 思路：

本题介绍两种思路解题，个人推荐思路一快速好理解
 思路一:
 1.先把其中一个链表的值变成负数
 2.遍历另一个链表第一个出现负数的值就是交点
 3.还原被改的链表
 思路二:
1.先用第一个链表的头节点head1搜索指针q遍历第一个链表直到为空，再把q放到head2上继续遍历
 2.用第二个链表的头节点head2搜索指针p遍历第一个链表直到为空，再把q放到head1上继续遍历
如果两个指针相等说明两个链表相交

三 代码：

#include <bits/stdc++.h>
using  namespace std;
/*
 * 思路一:
 * 1.先把其中一个链表的值变成负数
 * 2.遍历另一个链表第一个出现负数的值就是交点
 * 3.还原被改的链表
 */
typedef struct ListNode{
    int val;
    struct ListNode *next;
}ListNode;

ListNode *getIntersectionNode(ListNode *head1,ListNode *head2){

    ListNode *cur1=head1;//定义一个搜索指针
    //把第一个链表的值转化为负值
    while (cur1!=NULL){
        cur1->val=-(cur1->val);
        cur1=cur1->next;
    }
    ListNode *cur2=head2;
    ListNode *temp;//定义一个临时变量存储相交节点
    //遍历第二个链表找到第一个为负数的节点
    while(cur2!=NULL){
        if (cur2->val<0){
            temp=cur2;
            break;
        }
        cur2=cur2->next;
    }
    //还原链表
    cur1=head1;
    while (cur1!=NULL){
        cur1->val=-(cur1->val);
        cur1=cur1->next;
    }

    return temp;
}
/*
 * 思路二:
 * 1.先用第一个链表的头节点head1搜索指针q遍历第一个链表直到为空，再把q放到head2上继续遍历
 * 2.用第二个链表的头节点head2搜索指针p遍历第一个链表直到为空，再把q放到head1上继续遍历
 *  如果两个指针相等说明两个链表相交
 *  详解：
 *  其基本思想是使用两个指针 p 和 q 分别从 head1 和 head2 开始遍历，
 *  当其中一个指针到达链表末尾时，让它从另一个链表的头部重新开始遍历。
 *  这样，如果两个链表有相交节点，两个指针最终都会指向这个相交节点。
 *
 */

ListNode *getIntersectionNode2(ListNode *head1,ListNode *head2){
    ListNode *p=head1,*q=head2;
    while(p!=q){
        if(p!=NULL){
            p=p->next;
        }else{
            p=head2;
        }
        if(q!=NULL){
            q=q->next;
        }else{
            q=head1;
        }
    }
    return p;
}
int main() {
    // 创建第一个链表 1 -> 3 -> 5
    ListNode *head1 = (ListNode *)malloc(sizeof(ListNode));
    head1->val = 1;
    head1->next = (ListNode *)malloc(sizeof(ListNode));
    head1->next->val = 3;
    head1->next->next = (ListNode *)malloc(sizeof(ListNode));
    head1->next->next->val = 5;
    head1->next->next->next = nullptr;

    // 创建第二个链表 2 -> 4 -> 6 -> 3 -> 5
    ListNode *head2 = (ListNode *)malloc(sizeof(ListNode));
    head2->val = 2;
    head2->next = (ListNode *)malloc(sizeof(ListNode));
    head2->next->val = 4;
    head2->next->next = head1->next; // 交点，共享head1链表的3和5
    head2->next->next->next = head1->next->next;
    head2->next->next->next->next = nullptr;

    // 寻找并打印相交节点
//    ListNode *intersection = getIntersectionNode(head1, head2);
    ListNode *intersection = getIntersectionNode2(head1, head2);
    if (intersection != nullptr) {
        cout << intersection->val << endl;
    } else {
        cout << "-1" << endl;
    }

    // 释放链表占用的内存
    ListNode *temp;
    while (head1 != nullptr) {
        temp = head1;
        head1 = head1->next;
        free(temp);
    }
    while (head2 != nullptr) {
        temp = head2;
        head2 = head2->next;
        free(temp);
    }

    return 0;
}

四 小结

定义：两个不同的链表在某一点相交，即它们共享相同的节点。

特点：

• 可能完全没有相交，或者从某个节点开始完全相同。
• 相交点之后，两个链表的节点完全一致。

解题技巧：

1. 双指针法：两个指针分别从两个链表的头部开始遍历，当一个指针到达尾部时，从另一个链表的头部继续遍历。如果相交，两个指针最终会相遇。
2. 哈希表法：遍历其中一个链表，将节点地址存储在哈希表中，然后遍历第二个链表，检查节点是否已存在于哈希表中。