160相交lianbiao

160 相交链表

下面是题目

下面是题目给出的代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        
    }
};

• 首先我们要明白一个概念，什么是题目给出的相交节点？那就是地址是一样的，而不是val值一样的节点，这点非常关键，那么我们就要去找一下地址重合的那个节点

下面是给出的解

 class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        ListNode *commonNode = nullptr;
        int countA = 0, countB = 0;
        //老样子，双指针，解法
        if(headA!=nullptr&&headB!= nullptr)
        {
            //首先，我们要分别计算两个链表的长度
            int countA = 0;
            int countB = 0;
            ListNode *ptA = headA;
            ListNode *ptB = headB;
            while(ptA!= nullptr)
            {
                ptA=ptA->next;
                countA++;
            }
            while(ptB!= nullptr)
            {
                ptB=ptB->next;
                countB++;
            }
          	//计算完成后，两个都从头开始
             ptA = headA;
             ptB = headB;
            int temp = abs(countA-countB);
            if(countA>countB)//如果A比B长，那么A先走多出来的步数
            {
                for(int i = 0;i<temp;i++)
                {
                   ptA =ptA->next;
                }
            } else//否则，B先走多出来的步数
            {
                for(int i = 0;i<temp;i++)
                {
                    ptB =ptB->next;
                }
            }
            //现在两条链表的后续长度是一样的了，他们会同时走到commonnode，这时候我们只要
            //简单的做一个判断，就可以返回了！
            while (ptA!= nullptr &&ptB!= nullptr)
            {
                 if(ptA==ptB)
                 {
                     commonNode =ptA;
                     break;
                 }
                 ptA=ptA->next;
                 ptB=ptB->next;
            }
        }
        // 当然，如果上面没找到，呢么commonnode肯定是NULL了，直接返回即可
            return commonNode;

    }
};