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

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

提示：

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n

如果 listA 和 listB 没有交点，
intersectVal 为 0
如果 listA 和 listB 有交点，
intersectVal == listA[skipA + 1] == listB[skipB + 1]

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *A,*B,*p;

    //保证原链表结构不变
    A=headA;

    while(A!=NULL)
    {
        B=headB;
        while(B!=NULL)  //遍历链表B查看是否有交点
        {
            if(A==B)        //找到交点
            {
                p=A;    //结构体指针指向此相交结点
                return p;   //返回相交结点的地址
            }
            B=B->next;
        }
        A=A->next;
    }
    return NULL;    //执行到此处，说明没有相交结点，返回NULL，
}

进阶：
你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

官方题解


官方给出的代码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA == NULL || headB == NULL) {
        return NULL;
    }
    struct ListNode *pA = headA, *pB = headB;
    while (pA != pB) {
        pA = pA == NULL ? headB : pA->next;
        pB = pB == NULL ? headA : pB->next;
    }
    return pA;
}