My C++ code use stack, not good enough but easy to read


  • 1
    Y
    class Solution {
    public:
    	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    		stack<ListNode*> chain1,chain2;
    		while(headA!=NULL)
    		{
    			chain1.push(headA);
    			headA=headA->next;
    		}
    		while(headB!=NULL)
    		{
    			chain2.push(headB);
    			headB=headB->next;
    		}
    		ListNode* record=NULL;
    		while(!chain1.empty()&&!chain2.empty()&&chain1.top()==chain2.top())
    		{
    			record=chain1.top();
    			chain1.pop();
    			chain2.pop();
    		}
    		return record;
    	}
    };
    

    use too much extra space.


  • 0

    nice solution~


  • 0
    K

    Good solution by noticing that we should solve the problem backwards


  • 0
    Z

    But in this case, you can solve the problem in O(1) time, right?


  • 0
    Y

    maybe it's O(1) space? I think O(1) time is quite hard...
    I had wrote some other solutions, but they are not as easy to understand as this one use stack (I know it's silly...). I remembered that someone made a circle in the list to solve this problem, I cannot come out with a better one so I just put this stupid solution here


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.