链表相交 三种思路 C++ 代码

标签：head   cpp   finish   交换   while   地方   lang   null   思路   

方法1 回环法 讲listA & listB看成一个环

 
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //回环法 讲listA & listB看成一个环

        //e.g listA = [9,1,8,4,5]  listB = [1,8,4,5] 
        // posA=4 ,posB =5  
        // goon  posA=5 posB=9
        // goon posA= 1 ,posB=1  ,ok   finish
      
        ListNode * posA= headA,*posB = headB;
        bool AExchangeFlag=false;
        if(!headB  || !headA ) return NULL;
        while(!AExchangeFlag  || posA  ) 
        {
            if(posA == posB ) return posA;
            posA= posA->next;
            posB = posB->next;
            //在A没有执行交换情况下 
            if(!AExchangeFlag && posA== NULL ) { 
                AExchangeFlag=true;
                posA= headB;
            }
            if(posB==NULL ) posB = headA;
        }

        return NULL;
    }
};

方法2 stack 法，从后往前找到第一个不等的地方

 
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //stack 法，找到第一个不等的地方
             //e.g listA = [9,1,8,4,5]  listB = [1,8,4,5]  
            //  stackA =9 != listB=NULL, return --listA
        std::stack stackA, stackB;
        while(headA)
        {
            stackA.push(headA);
            headA= headA->next;
        }
        while(headB)
        {
            stackB.push(headB);
            headB = headB->next;
        }
         if(stackA.size()

方法3 对齐法 先计算出长度差

 
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
          // 对齐法 先计算出长度差 
            // listA = [9,1,8,4,5]  listB = [7,8,4,5] 
            // posA= 1 ,posB=7
            // posA=8 ,pos=8  ok 
             
        auto posA= headA, posB= headB;
        //to get lenA ,lenB
        int lenA=0,lenB=0;
        while(posA) {
            lenA++;
            posA= posA->next;
        }
              while(posB)
               {
            lenB++;
            posB= posB->next;
        }
         if(lenA next;  
              difLen--;
          }
         

        //now same len
        posB=  headB;
         while(posA)
         {
             if(posA == posB) return posA;
            posA= posA -> next;
            posB= posB -> next;
         }
        
        return NULL;

    }
};

链表相交 三种思路 C++ 代码

标签：head   cpp   finish   交换   while   地方   lang   null   思路   

原文地址：https://www.cnblogs.com/boyang987/p/14771416.html