[数据结构与算法]160 相交链表

题目描述

原题链接
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

题目分析

一开始理解错了题意，以为相交的意思是从两个链表分别从某个节点开始后面的节点的值相同，实际上是节点相同，节点相同比节点的值相同要更加严格。
因此一种方法是可以用哈希集合，快速找出某个链接出现在另一个链表的第一个节点。这种方法的空间复杂度是O（n）。考虑空间复杂度为O（1）的方法，可以虚构两个新的链表C和D，C=A+B，D=B+A，使用双指针分别遍历这两个链表，直到两个指针指向的节点相同，返回这个相同的节点即可。

代码

这里给出第二种思路的方法。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *n1 = headA, *n2 = headB;
        if(n1 == NULL || n2 == NULL){
            return NULL;
        }
        while(n1 != n2){
            n1 = n1 == NULL? headB:n1->next;
            n2 = n2 == NULL? headA:n2->next;
        }
        return n1;
    }
};