Untitled

mail@pastecode.io avatar
unknown
plain_text
5 months ago
879 B
0
Indexable
Never
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        
        int m = 0, n = 0;
        
        while(curA != null) {
            curA = curA.next;
            m++;
        } //O(m)
        while(curB != null) {
            curB = curB.next;
            n++;
        } //O(n)
        
        curA = headA;
        curB = headB;
        
        if(m > n) {
            for(int i = 0; i < m-n; i++) {
                curA = curA.next;
            }
        } else {
            for(int i = 0; i < n-m; i++) {
                curB = curB.next;
            }
        } //O(|m-n|)
        while(curA != curB) {
            curA = curA.next;
            curB = curB.next;
        } //O(i)
        return curA;
    }
} // T: O(m + n + |m-n| + i) where i < m,n; S: O(1)