My JAVA answer run in O(n) time and use only O(1) memory


  • 1
    N

    public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB)
    {
    if(headA == null || headB == null)
    return null;
    int n = 1;
    int m = 1;
    ListNode p,q;
    p = headA;
    while(p.next != null)
    {
    n++;
    p = p.next;
    }
    p = headB;
    while(p.next != null)
    {
    m++;
    p = p.next;
    }
    p = headA;
    q = headB;
    if(n < m)
    {
    for(int i = 1;i <= m -n;i++)
    q = q.next;
    }
    else
    if(n > m)
    {
    for(int i = 1;i <= n - m;i++)
    p = p.next;
    }
    while(p != null && p != q)
    {
    p = p.next;
    q = q.next;
    }
    return p;
    }
    }


  • 1
    J

    Very good solution! Inspired by your solution, following is my c++ solution.

    // time: O(n); memory: O(1);
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        
        ListNode *rootA = headA, *rootB = headB;
        
        while (lenA > lenB) {
            rootA = rootA->next;
            --lenA;
        }
        
        while (lenB > lenA) {
            rootB = rootB->next;
            --lenB;
        }
        
        while (rootA != nullptr && rootA != rootB) {
            
            rootA = rootA->next;
            rootB = rootB->next;
        }
        
        return rootA;
        
    }
    
    int getLength(ListNode *root) {
        
        int len = 0;
        
        while (root != nullptr) {
            root = root->next;
            ++len;
        }
        
        return len;
    }

Log in to reply
 

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