C++ using two pointers


  • 0
    X
    class Solution {
    public:
        // create a cycle and find the start point of cycle, then recover the list.
        // yes , that`s  Tortoise and Hare
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            if(headA == NULL || headB == NULL){
                return NULL;
            }
            ListNode* tailA = headA;
            while(tailA->next != NULL){
                tailA = tailA->next;
            }
            tailA->next = headA;
            ListNode* slow = headB;
            ListNode* fast = headB;
            bool intersect = false;
            while(fast != NULL && fast->next != NULL){
                slow = slow->next;
                fast = fast->next->next;
                if(slow == fast){
                    intersect = true;
                    break;
                }
            }
            if(intersect == true){
                slow = headB;
                while(slow != fast){
                    slow = slow->next;
                    fast = fast->next;
                }
                tailA->next = NULL;
                return slow;
            }
            tailA->next = NULL;
            return NULL;
        }
    };

Log in to reply
 

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