O(m+n) time and O(1) space solution


  • 0
    Z

    a straight forward solution

    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null && headB == null) {
                return null;
            } else if (headA == null || headB == null) {
                return null;
            } else if (headA == headB) {
                return headA;
            }
            
            int lenA = getLength(headA);
            int lenB = getLength(headB);
            int count = Math.abs(lenA - lenB);
            
            while (count > 0) {
                if (lenA > lenB) {
                    headA = headA.next;
                } else {
                    headB = headB.next;
                }
                count--;
            }
            if (headA == headB) { // a corner case: two lists intersect at the tail
                return headA;
            }
            while (headA != null && headB != null && headA != headB) {
                headA = headA.next;
                headB = headB.next;
                if (headA == headB) {
                    return headA;
                }
            }
            return null;
        }
        
        private int getLength(ListNode head) {
            int len = 0;
            while (head != null) {
                len++;
                head = head.next;
            }
            return len;
        }
    }

Log in to reply
 

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