面试题 02.07. 链表相交

面试题 02.07. 链表相交

• 题号：力扣面试题 02.07
• 知识点：链表
• 目标完成度：56/150
• 总结
  题干：
  
  
  

思路：

• 1.先看下题目，题目比较长，大致意思是找到从后往前的公共子串的第一个结点。看到这个题目想到了一个类似的题目14. 最长公共前缀。
  
• 2.14题这个比较简单，就是求字符串的最长公共前缀，而本题实际上可以理解为求最长公共后缀的问题。
• 3.根据以上思路，可以先求出headA和headB的链表长度，假设headA的长度大于headB，计算出他们的长度之差为delta
• 4.然后先让指向headA的指针cur往后走delta 步，让cur和指向headB的指针curB的链表长度相等，然后再判断cur和curB的链表结点是否相同(类似于判断字符串后缀是否相同)，如果相同的话就返回cur，如果不同就同时后移一个结点再进行判断，如此循环直到链尾。
• 5.如果到链尾都没有找到相同的后缀，则说明两个链表不存在交点，返回nullptr

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 求A链表的长度
        ListNode *cur = headA;
        int sizeA = 0;
        while(cur != nullptr){
            cur = cur->next;
            sizeA++;
        }
        // 求B链表的长度
        cur = headB;
        int sizeB = 0;
        while(cur != nullptr){
            cur = cur->next;
            sizeB++;
        }
        // 分两种情况，A比B长或B比A长
        if (sizeA > sizeB){
            // 求A链表和B链表的长度差
            int delta = sizeA - sizeB;
            cur = headA;
            // 先让A前移到和B一样长的位置
            while(delta--){
                cur = cur->next;
            }
            ListNode *curB = headB;
            while(cur != nullptr){
                // 当后面的结点都相等时，为交点
                if (cur == curB){
                    return cur;
                }
                cur = cur->next;
                curB = curB->next;
            }
        }
        // 同理
        else{
            int delta = sizeB - sizeA;
            cur = headB;
            while(delta--){
                cur = cur->next;
            }
            ListNode *curA = headA;
            while(cur != nullptr){
                if (cur == curA){
                    return cur;
                }
                cur = cur->next;
                curA = curA->next;
            }  
        }
        // 执行到这一步说明遍历完了也没有找到交点
        return nullptr;
    }
};