讨论/《中级算法》 - 相交链表/
《中级算法》 - 相交链表

相交链表

  1. 很迷这个输入,样例给的跟参数都不一致,诶,但是不影响做题
  2. 判断链表是否相交,跟链表元素的值val无关,比较时判断指针指向的地址是否是同一个地址即可p == q
  3. 遍历两个链表,获取各自长度,较长的先移动两者相差的长度,借此达到两者能够同时到达末尾,然后两个链表同时移动,如果指针pq同时指向同一个地址p == q,则说明链表相交,否则返回null
  4. 若长度相同,则直接同时移动判断
class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        int aLength = 0;
        int bLength = 0;
        ListNode *p = headA;
        ListNode *q = headB;
        // 计算链表长度
        while (p != nullptr)
        {
            p = p->next;
            aLength++;
        }
        while (q != nullptr)
        {
            q = q->next;
            bLength++;
        }
        p = headA;
        q = headB;
        // 移动较长指针至 两个链表剩余长度一致
        if (aLength > bLength)
        {
            int differenceLength = aLength - bLength;
            for (int i = 0; i < differenceLength; i++)
            {
                p = p->next;
            }
        }
        else if (aLength < bLength)
        {
            int differenceLength = bLength - aLength;
            for (int i = 0; i < differenceLength; i++)
            {
                q = q->next;
            }
        }
        // 遍历链表 找是否存在相交节点
        while(p != nullptr)
        {
            if(p == q)
            {
                return p;
            }
            p = p->next;
            q = q->next;
        }
        return nullptr;
    }
};
展开全部 11 讨论