Intersection of Two Linked Lists

160. Intersection of Two Linked Lists

https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1215/

Explore - LeetCode

Language: C++

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        while (headA != nullptr) {
            ListNode *pB = headB;
            while (pB != nullptr) {
                if (headA == pB) return headA;
                pB = pB->next;
            }
            headA = headA->next;
        }
        return nullptr;
    }
};


class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        set<ListNode *> nodes_in_B;

        while (headB != nullptr) {
            nodes_in_B.insert(headB);
            headB = headB->next;
        }

        while (headA != nullptr) {
            // if we find the node pointed to by headA,
            // in our set containing nodes of B, then return the node
            if (nodes_in_B.find(headA) != nodes_in_B.end()) {
                return headA;
            }
            headA = headA->next;
        }

        return nullptr;
    }
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pA = headA;
        ListNode *pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
        // Note: In the case lists do not intersect, the pointers for A and B
        // will still line up in the 2nd iteration, just that here won't be
        // a common node down the list and both will reach their respective ends
        // at the same time. So pA will be NULL in that case.
    }
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *temp = headA;
        int len1 = 0;
        while (temp) {
            len1++;
            temp = temp->next;
        }
        
        temp = headB;
        int len2 = 0;
        while (temp) {
            len2++;
            temp = temp->next;
        }
        
        int diff = abs(len1 - len2);
        if (len1 > len2) {
            while (diff) {
                headA = headA->next;
                diff--;
            }
        } else {
            while (diff) {
                headB = headB->next;
                diff--;
            }
        }
        
        while (headA && headB) {
            if (headA == headB) return headA;
            headA = headA->next;
            headB = headB->next;
        }
        
        return NULL;
    }
};

 

시도

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    
    
public:
    class ListNode2 {
    public:
        int val;
        ListNode* prev;
        ListNode* next;
        ListNode2* realNext;
        ListNode2(int x) : val(x), prev(NULL), next(NULL) {}
        ListNode2(int x, ListNode* prev, ListNode* next) : val(x), prev(prev), next(next) {}
    };
    
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode2* nodeA = new ListNode2(headA->val, NULL, headA->next);
        ListNode2* nodeB = new ListNode2(headB->val, NULL, headB->next);
        
        ListNode* nodeAA = headA;
        ListNode* nodeBB = headB;
        
        while (nodeA) {
            nodeA->realNext = new ListNode2(headA->next->val, headA, headA->next);
            headA = headA->next;
            nodeA = nodeA->realNext;
        }
        
        while (nodeB) {
            nodeB->realNext = new ListNode2(headB->next->val, headB, headB->next);
            headB = headB->next;
            nodeB = nodeB->realNext;
        }
        
        if (nodeA->val != nodeB->val)
            return NULL;
        
        while (nodeA->next != nodeB->next) {
            nodeA = nodeA->realNext;
        }
        
        while (nodeAA->next != nodeA->next)
            nodeAA = nodeAA->next;
        
        return nodeAA;
        
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    
    
public:
    
    bool returnMatchNodes(ListNode *headA, ListNode *headB) {
        bool isMatch = false;
        
        while (headA-> val && headA) {
            
            while (headB->val && headB) {
                if (headA->val == headB->val) {
                    isMatch = true;
                    break;
                }
            }
            
            if (isMatch)
                break;
            
        }
        
        return isMatch;
    }
    
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
       
        bool isMatch = true;
        ListNode* result;
        
        while (headA) {
            
            isMatch = returnMatchNodes(headA, headB);
            
            while (isMatch && headA) {
                result = headA;
                if (headA->val != headB->val) {
                    isMatch = false;
                }  
            }
            
            if(!isMatch)
                break;
            else
                return headA;
            
        }
        
        return NULL;
        
    }
};

문제점

솔루션은 3가지였는데

1) brute force : 이중 포문으로, time : O(N * M), space : O(1)

2) hash table : time : O(N + M), space : O(M)

3) two pointer : time : O(N + M), space : O(1)

부르트 포스랑 해시 테이블을 생각했었는데 하기 싫어서

맨 뒤로 이동하고, prev 도 저장하게 해서 같은 데서 시작해서 안 같을 때까지 찾으려는 방법을 생각했었는데 제대로 못했다.

솔루션 코드블럭의 맨 마지막 코드는 두 head의 전체 길이를 구하고 다른 부분만큼만 각각 이동시켜서

같을 경우 리턴하고, 동시에 하나씩 진행시키도록 하는 방법으로 진행한다.  -> 이렇게 풀고 싶다 ㅠㅠㅠㅠ