代码随想录-DAY④-相交链表经典三解——leetcode 160

解法一：哈希集合

思路

将链表 A 中的每个节点都存入哈希集合，

遍历链表 B 并判断每一个节点，

如果发现已存在在哈希集合中的，说明相交， 

如果遍历结束，说明不相交。

时间复杂度：O(m+n)

空间复杂度：O(m)

代码

/**
 * 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) {
        unordered_set<ListNode *> visited;
        ListNode * visit = headA;
        while(visit != nullptr){
            visited.insert(visit);
            visit = visit->next;
        }

        visit = headB;
        while(visit != nullptr){
            if(visited.count(visit)){
                return visit;
            }
            visit = visit->next;
        }
        return nullptr;
    }
};

解法二：长度对齐

思路

遍历并计算两个链表的长度差，

让指向较长链表的指针向后挪动长度差的步数，

然后两个指针同时向后移动，

每走一步判断是否相等，

发现相等则存在相交，

走到头（一定同时）都不相等说明不相交。

时间复杂度：O(m+n)

空间复杂度：O(1)

代码

/**
 * 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 *ptrA = headA, *ptrB = headB;
        int lenA = 0, lenB = 0;
        while (ptrA != nullptr) {
            lenA++;
            ptrA = ptrA->next;
        }
        while (ptrB != nullptr) {
            lenB++;
            ptrB = ptrB->next;
        }

        ptrA = headA, ptrB = headB;
        if (lenA > lenB) {
            for (int i=0; i<lenA-lenB; i++) {
                ptrA = ptrA->next;
            }
        } else if (lenA < lenB) {
            for (int i=0; i<lenB-lenA; i++) {
                ptrB = ptrB->next;
            }
        }

        while (ptrA != nullptr) {
            if (ptrA == ptrB) {
                return ptrA;
            }
            ptrA = ptrA->next;
            ptrB = ptrB->next;
        }
        return nullptr;
    }
};

解法三：双指针对调

思路

两个指向链表的指针同时向后移动，

任意一个走到头后，

都继而指向另一个链表头，

然后继续同时移动，

即最终两个指针一定走了一样的步数（n+m），

所以如果存在相交，

最后一定有一小段两指针重叠移动。

时间复杂度：O(m+n)

空间复杂度：O(1)

代码

/**
 * 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 *ptrA = headA, *ptrB = headB;
        while(ptrA != ptrB){
            ptrA = ptrA==nullptr?headB:ptrA->next;
            ptrB = ptrB==nullptr?headA:ptrB->next;
        }
        return ptrA;
    }
};

原文地址：https://blog.csdn.net/weixin_43160551/article/details/140237621

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！