Intersection of Two Linked Lists Solutions in C++

// Source : https://oj.leetcode.com/problems/intersection-of-two-linked-lists/
// Author : Hao Chen
// Date   : 2014-12-01



/**
 * 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) {

            //caculate the length of each List
            int lenA = getListLength(headA);
            int lenB = getListLength(headB);

            if (lenA<=0 || lenB<=0 ) return NULL;

            //let List A is the longest List;
            if (lenA < lenB){
                swap(headA, headB);
            }

            //move head of List A, make both of Lists are same length 
            for (int i=0; i<abs(lenA-lenB); i++){
                headA = headA->next;
            }

            //synced travel both of Lists and check their nodes are same or not 
            while (headA != headB){
                headA = headA->next;
                headB = headB->next;
            }

            return headA;
        }
    private:    
        inline int getListLength(ListNode *head){
            int len=0;
            while(head!=NULL){
                head = head->next;
                len++;
            }
            return len;
        }
};

/// Source : https://leetcode.com/problems/intersection-of-two-linked-lists/description/
/// Author : liuyubobobo
/// Time   : 2018-10-01

#include <iostream>

using namespace std;

/// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


/// Brute Force
/// Time Complexity: O(m*n)
/// Space Complexity: O(1)
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

        for(ListNode* pA = headA; pA; pA = pA->next)
            for(ListNode* pB = headB; pB; pB = pB->next)
                if(pA == pB)
                    return pA;
        return NULL;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/intersection-of-two-linked-lists/description/
/// Author : liuyubobobo
/// Time   : 2018-10-01

#include <iostream>
#include <unordered_set>

using namespace std;

/// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


/// Using HashSet
/// Time Complexity: O(m + n)
/// Space Complexity: O(m)
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

        unordered_set<ListNode*> set;
        for(ListNode* pA = headA; pA; pA = pA->next)
            set.insert(pA);

        for(ListNode* pB = headB; pB; pB = pB->next)
            if(set.count(pB))
                return pB;

        return NULL;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/intersection-of-two-linked-lists/description/
/// Author : liuyubobobo
/// Time   : 2018-10-01

#include <iostream>
#include <unordered_set>

using namespace std;

/// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


/// Two Pointers
/// Time Complexity: O(m + n)
/// Space Complexity: O(1)
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

        ListNode* pA = headA;
        ListNode* pB = headB;
        while(pA || pB){

            if(pA == pB)
                return pA;

            if(pA) pA = pA->next;
            else pA = headB;

            if(pB) pB = pB->next;
            else pB = headA;
        }

        return NULL;
    }
};


int main() {

    return 0;
}