160. Intersection of Two Linked Lists

Leetcode link

解题思路——拼接

题目要求我们找出两个链表 A、B 第一个相交的节点

第一个思路就是拼接，我们需要做三个操作：

• 把链表 A 的尾巴拼接上链表 B 得到链表 C
• 把链表 B 的尾巴拼接上链表 A 得到链表 D
• 从头到尾同时遍历链表 C 和 D，找到第一个相同的元素就是链表 A、B 第一个相交的节点

C++

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p=headA;
        ListNode *q=headB;
          // flag 表示还没经过拼接，在遍历到链表尾的时候需要做一下拼接
        bool flagA = true;
        bool flagB = true;

        while(p != q) {
            if(p == nullptr && flagA) {
                  // 只需要拼接一次，不然如果没有交点的话会一直循环下去
                flagA = false;
                p = headB;
            } else {
                p = p->next;
            }

            if(q == nullptr && flagB) {
                flagB = false;
                q = headA;
            } else {
                q = q->next;
            }
        }
        // 找到第一个相同的就是所求节点，如果没有就是 nullptr
        return p;
    }
};

解题思路——计算长度

这个思路也挺有意思的

我们知道两个有相交节点的相交部分长度是一样的，所以我们只需要计算两个链表的长度差 diff

然后将较长的那个链表先遍历 diff 个元素，这样一来两个链表剩下的长度就想等了

最后我们只需要同时遍历两个链表的剩余部分比较是否相同就好

C++

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p=headA;
        ListNode *q=headB;
        int lenA = 0;
        int lenB = 0;

        // 计算两个链表长度
        while(p != nullptr) {
            lenA++;
            p = p->next;
        }
        while(q != nullptr) {
            lenB++;
            q = q->next;
        }

        int diff;
        // 把 p 指向比较长的链表
        if(lenA > lenB) {
            diff = lenA - lenB;
            p = headA;
            q = headB;
        } else {
            diff = lenB - lenA;
            p = headB;
            q = headA;
        }

        // 将比较长的那个链表先遍历一点
        while(diff-- > 0) {
            p = p->next;
        }

        // 这个时候两个链表剩余部分长度相同，直接一起遍历就好
        while(p != q) {
            p = p->next;
            q = q->next;
        }

        return p;
    }
};