Leetcode/offer52get_Intersection-Node.cpp at main · yayajjiang/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
 * 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) {
        //stack, go from back to front
        stack<ListNode *> sA;
        stack<ListNode *> sB;
        ListNode* tempA = headA;
        ListNode* tempB = headB;
        while(tempA!=nullptr){
            sA.push(tempA);
            tempA = tempA->next;
        }
         while(tempB!=nullptr){
            sB.push(tempB);
            tempB = tempB->next;
        }
        ListNode *ans = nullptr;
        while(!sA.empty() && !sB.empty() && sA.top() == sB.top()){
            ans = sA.top();//needs to store the value and then return
            sA.pop();
            sB.pop();

        }
        return ans;

        //two pointers
        // if(headA == nullptr || headB == nullptr) return nullptr;
        // ListNode* tempA = headA;
        // ListNode* tempB = headB;
        // while(tempA != tempB){
        //     tempA = tempA == nullptr ? headB: tempA->next;
        //     tempB = tempB == nullptr ? headA: tempB->next;
        // }
        // return tempA;

        //brute force
        // ListNode* tempA = headA;
        // ListNode* tempB = headB;
        // while(tempB){
        //     while(tempA){
        //         if(tempA != tempB){
        //             tempA = tempA->next;
        //         }else{
        //             return tempA;
        //         }

        //     }
        //     tempA = headA;//remember to initialize
        //     tempB = tempB->next;
        // }
        // return nullptr;

        //set
        // unordered_set<ListNode *> visited;
        // ListNode *temp = headA;
        // while (temp != nullptr) {
        //     visited.insert(temp);
        //     temp = temp->next;
        // }
        // temp = headB;
        // while (temp != nullptr) {
        //     if (visited.count(temp)) {
        //         return temp;
        //     }
        //     temp = temp->next;
        // }
        // return nullptr;
    }
};