my solution with O(n+m) time and O(1) space . using reverse method.


  • 0
    H

    algorithm:

    1. give list headA and headB.we can get the length a+1+c=count(headA) ,b+1+c=count(headB) //the 1 of (a+1+c) means the intersection c1
    2. reverse the headA , then we get the length b+1+a=count(headB).
    3. because we can't break the list,so we reverse headA again.
    4. finally , we can get the length of a , b and c. if the a-th of headA== the b-th of headB , return headA, else return NULL.
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *reverse(ListNode* head){
            ListNode* top=NULL;
            ListNode*p=head;
            ListNode*q;
            while(p!=NULL){
                q=p->next;
                p->next=top;
                top=p;
                p=q;
            }
            return top;
        }
        int count(ListNode *head){
            int count=0;
            while(head!=NULL){
                count++;
                head=head->next;
            }
            return count;
        }
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            int ac=count(headA);
            int bc=count(headB);
            if(ac==0||bc==0){
                return NULL;
            }
            
            headA=reverse(headA);
            int ab=count(headB);
            int b=(ab-ac+bc)/2;
            int c=bc-b;
            int a=ac-c;
            headA=reverse(headA);
            while(headA!=NULL&&a--){
                headA=headA->next;
            }
            while(headB!=NULL&&b--){
                headB=headB->next;
            }
            if(headA==headB){
                return headA;
            }else{
                return NULL;
            }
        }
    };
    

Log in to reply
 

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