Original Java Solution(not simple), using reverse of list. O(n) time and O(1) space.


  • -1
    M
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        int na = length(headA);
        int nb = length(headB);
        ListNode tailb = reverse(headB);
        int sumWoCommon = length(headA) - 1;
        reverse(tailb);
        
        if (tailb != next(headA, na - 1)) {
            return null;
        }
        
        int common = (na + nb - sumWoCommon) / 2;
        reverse(tailb);
        
        return next(headA, na - common);
        
    }

Log in to reply
 

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