跳转至

160 相交链表

leetcode

容易理解的方法

  1. 计算两个链表的长度
  2. 计算长度差gap
  3. 长的一侧先走gap个长度,走完后,两个链表处于同一长度
  4. 两个链表同时遍历,如果p1 == p2,则相遇;如果p1(p2) == nullptr,说明无法相遇
/**
 * 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) {
        ListNode *p1 = headA, *p2 = headB;
        int lenA = 0, lenB = 0;
        while (p1) {
            lenA++;
            p1 = p1->next;
        }
        while (p2) {
            lenB++;
            p2 = p2->next;
        }
        p1 = headA;
        p2 = headB;
        if (lenB > lenA) {
            swap(lenB, lenA);
            swap(p1,p2);
        }
        int gap = lenA - lenB;
        while (gap--) {
            p1 = p1->next;
        }
        while (p1) {
            if(p1 == p2)
                return p1;
            p1 = p1->next;
            p2 = p2->next;
        }
        return nullptr;
    }
};
  • 时间复杂度:O(n + m)
  • 空间复杂度:O(1)

难以理解的方法

picture 0

第一轮:

各自遍历链表,短的一侧到达终点需要走A+C,而长的一侧到达终点需要走B+C,长度之差为B-A。

picture 1

如果想要抹平两者之间长度之差,使两者同时到达相交点,那么需要让短的一侧比长的一侧多走B-A。我们发现,当短的一侧到达终点,长的一侧需要走B-A才能到达终点,若此时让短的一侧转为走长的一侧,那么当长的一侧到达终点,短的一侧恰好弥补了B-A的长度差,此时两者步数之和相同。

picture 2

第二轮: 各自遍历链表,两者相遇即为相交点。如果不相遇,则没有相交。

结论:

由于每个指针都需要走A + B + C,两个指针最后一定相等 - 如果两个指针都为nullptr,说明没有相交点 - 否则,两个指针等于相交点指针

/**
* 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) {
        ListNode* p1 = headA, * p2 = headB;
        while(p1 != p2){
            if(p1 == nullptr)
                p1 = headB;
            else
                p1 = p1->next;
            // 注意这里是if,因为p1和p2的判断是互相独立的
            if(p2 == nullptr)
                p2 = headA;
            else
                p2 = p2->next;
        }
        return p1;
    }
};
/**
* 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) {
        // 有一方为空,肯定不相交
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }
};