每日一题--判断两个链表相交

悠悠 2023-02-26 13:27 67阅读 0赞

今天这道是面试中的高频题，有关链表和树的操作一直都是面试官比较喜欢考的，因为链表和树的操作涉及到指针的使用，面试官可以通过算法题的形式短时间内考察一个人对指针的熟练程度。话不多说，先来看题。  
**题目描述**  
　　判断两个单链表是否相交 ，并返回第一个相交的元素。  
**思路**  
　　可以想到，如果两个链表相交，那么它肯定是尾部相连，首部分开，就像朝左侧卧的“Y”形。因此，能够想到两种思路，一种是从后往前遍历链表，直到两个链表的某个结点元素值不相等，那这个结点的前一个结点就是第一个相交的结点。另外一种思路就是从前往后遍历，首先拿到两个链表的长度，将两个链表的长度差记录下来，长链表先走长度差步，然后长短链表再一起走，直到遇到两个链表的结点值相等，即为第一个相交的结点。具体梳理如下：  
　　思路一：用两个栈存储两个链表的结点，然后依次比较两个栈顶结点，若相同则说明相交，直到两个结点不同，则说明这个结点的前一个结点是第一个相交的结点。　　  
　　思路二：依次遍历两个链表，记录长度，然后让长链表先走长度差步，两链表再同时走，直到两个结点相同，则为第一个相交的结点。  
**代码实现**

//链表结点
    struct ListNode{
        
     int val;
     struct ListNode* next;
     ListNode(int v): val(v), next(nullptr){
        }
    };
    
    //思路一
        ListNode* FindFirstCommonNode(ListNode *headA, ListNode *headB) {
        
            stack<ListNode*> sa,sb;
            ListNode* curA,*curB;
            curA = headA;
            curB = headB;
            while(curA!=nullptr){
        
                sa.push(curA);
                curA = curA->next;
            }        
            while(curB!=nullptr){
        
                sb.push(curB);
                curB = curB->next;
            }
            int n = 0;
            int size = sa.size();
            while(!sa.empty()&&!sb.empty()){
        
                if(sa.top()!=sb.top())
                    break;
                else{
        
                    sa.pop();
                    sb.pop();
                    n++;
                }
            }
            n = size-n;
            while(n--){
        
                headA = headA->next;
            }
            return headA;
        }
    
    //思路二
     ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        
            int len1 = 0, len2 = 0;
            ListNode* pcur1 = pHead1;
            ListNode* pcur2 = pHead2;
            while(pcur1 != nullptr){
        
                len1++;
                pcur1 = pcur1->next;
            }
            while(pcur2 != nullptr){
        
                len2++;
                pcur2 = pcur2->next;
            }
            ListNode* plong = nullptr;
            ListNode* pshort = nullptr;
            int k = 0;
            if(len1 > len2){
        
                plong = pHead1;
                pshort = pHead2;
                k = len1 - len2;
            }
            else{
        
                plong = pHead2;
                pshort = pHead1;
                k = len2 - len1;
            }
            while(k--){
        
                plong = plong->next;
            }
            while(plong->next != nullptr && plong != pshort){
        
                plong = plong->next;
                pshort = pshort->next;
            }
            if(plong == pshort){
        
                return plong;
            }
            return nullptr;
        }

由于同一道算法题有无数种解法，我所写出来的不一定是最优解，如果有小伙伴有更好的想法，欢迎提出来，一起交流。另外，在刷题的路上，一个人总是孤独的，为此，我建了一个公众号，每天打卡一道题，欢迎小伙伴们加入~  
　　![在这里插入图片描述][20200715220308880.jpg]

[20200715220308880.jpg]: /images/20230209/8497bd4d1f3945fbab2256806ed1e67d.png