List intersection

Job title: Software Development Engineer (SDE II)
Interview type: Phone Screen

Problem Statement

Given two singly linked lists, determine if the two lists interest. Return the intersecting node. Note that the intersection is defined based on reference, not value. That is, if the k-th node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then there are intersecting.

Hints:

20: You can do this in O(A + B) and O(1) additional space. That is, you do not need a hash table (although you could do it with one).
45: Examples will help you. Draw a picture of intersecting linked lists and two equivalent linked lists (by value) that do not intersect.
55: Focus on first identifying if there is an intersection.
65: Observe that 2 intersecting linked lists will always have the same last node. Once they intersect all the nodes after that will be equal.
76: You can determine if 2 linked lists intersect by traversing to the end of each and comparing their tails.
93: Now, you need to figure out where the linked lists intersect. Suppose the linked lists were the same length. How could you do this?
111: If the 2 linked lists were the same length, you could traverse forward in each until you found an element in common. Now, how do you adjust this for lists of different lengths?
120: Try using the difference between the lengths of the two linked lists.
129: if you move a pointer in the longer linked lists forward by the difference in length. You can then apply a similar approach to the scenario where the lists are equal.

Solution

LeetCode Intersection of Two Linked Lists

Runtime: 1 ms, faster than 99.37% of Java online submissions for Intersection of Two Linked Lists.
Memory Usage: 42.4 MB, less than 73.89% of Java online submissions for Intersection of Two Linked Lists.

package com.andrew;

public class Main {

    // Driver method
    public static void main(String[] args) {
        Solution solution = new Solution();

        ListNode listA = new ListNode("a");
        ListNode b = new ListNode("b");

        ListNode listB = new ListNode("p");
        ListNode q = new ListNode("q");

        ListNode c = new ListNode("c");
        ListNode d = new ListNode("d");
        ListNode e = new ListNode("e");
        ListNode f = new ListNode("f");
        ListNode g = new ListNode("g");

        listA.next = b;
        b.next = c;

        listB.next = q;
        q.next = c;

        c.next = d;
        d.next = e;
        e.next = f;
        f.next = g;

        solution.getIntersectionNode(listA, listB);
    }

    public static class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            int sizeA = getSize(headA);
            int sizeB = getSize(headB);
            int offset  = Math.abs(sizeA - sizeB);
            if (sizeA > sizeB) {
                headA = adjust(headA, offset);
            } else {
                headB = adjust(headB, offset);
            }
            return compare(headA, headB);
        }

        private ListNode compare(ListNode a, ListNode b) {
            ListNode intersection = null;
            while (intersection == null && a != null && b != null) {
                intersection = a == b ? a : null;
                a = a.next;
                b = b.next;
            }
            return intersection;
        }

        private ListNode adjust(ListNode node, int offset){
            while (offset > 0 && node != null && node.next != null) {
                node = node.next;
                offset--;
            }
            return node;
        }

        private int getSize(ListNode root) {
            int counter = 0;
            ListNode node = root;
            while (node != null) {
                counter++;
                node = node.next;
            }
            return counter;
        }
    }

      public static class ListNode {
      String val;
      ListNode next;
      ListNode(String x) {
          val = x;
          next = null;
      }
  }

}