Intersection of Two Linked Lists (求两个单链表的相交结点)

灰太狼 2022-01-05 10:39 77阅读 0赞

题目描述：

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                       ↘
                         c1 → c2 → c3
                       ↗            
    B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

*  If the two linked lists have no intersection at all, return `null`.
 *  The linked lists must retain their original structure after the function returns.
 *  You may assume there are no cycles anywhere in the entire linked structure.
 *  Your code should preferably run in O(n) time and use only O(1) memory.

solution：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL)
            return NULL;
        int lenA = 0;
        int lenB = 0;
        ListNode *pA = headA;
        while (pA != NULL)
        {
            ++lenA;
            pA = pA->next;
        }
        ListNode *pB = headB;
        while (pB != NULL)
        {
            ++lenB;
            pB = pB->next;
        }
    
        if (pA != pB)
            return NULL;
    
        pA = headA;
        pB = headB;
        
        if (lenA > lenB)
        {
            int k = lenA - lenB;
            while (k--)
            {
                pA = pA->next;
            }
        }
        else
        {
            int k = lenB - lenA;
            while (k--)
            {
                pB = pB->next;
            }
        }
        
        while (pA != pB)
        {
            pA = pA->next;
            pB = pB->next;
        }
        return pA;
    }

上述解法来自《剑指offer》，还有一种基于Hashset的方法。

solution：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL)
            return NULL;
        unordered_set<ListNode*> st;
        while (headA != NULL)
        {
            st.insert(headA);
            headA = headA->next;
        }
        
        while (headB != NULL)
        {
            if (st.find(headB) != st.end())
                return headB;
            headB = headB->next;
        }
        return NULL;
    }

转载于:https://www.cnblogs.com/gattaca/p/4671846.html