Monday, October 03, 2016

find intersection of linked lists

O(m+n) time, O(1) space. No changes to linked lists.
(head1, head2):
    if head1 == null || head2 == null:
        return null
    count1 = getcount(head1)
    count2 = getcount(head2)
    delta = count1 - count2
    n1 = head1, n2 = head2
    if delta > 0:
        for i = 0, i < delta, i++:
            n1 = n1.next
    else if delta < 0:
        for i = 0, i < abs(delta), i++:
            n2 = n2.next
    intersection = null
    while n1 != null: // or n2 != null
        if n1 == n2:
            intersection = n1
            break
        n1 = n1.next
        n2 = n2.next
    return intersection
[Hat tip to AJ]

No comments:

Post a Comment