I know my naming is not good. Please exclude variable / function renaming reviews from your comments.
import java.util.NoSuchElementException;
/**
* http://stackoverflow.com/questions/2216666/finding-the-intersecting-node-from-two-intersecting-linked-lists
*/
public class Interserction {
private Node first;
private Node last;
private int size;
public void add (int element) {
final Node l = last;
final Node newNode = new Node(element, null);
last = newNode;
if (first == null) {
first = newNode;
} else {
l.next = newNode;
}
size++;
}
public void attach (Interserction l, int item) {
if (l == null) {
throw new NullPointerException("The input linkedlist is null.");
}
if (l.last == null) {
throw new NoSuchElementException("The last element of linkedlist is null");
}
if (first == null) {
throw new NoSuchElementException("The linked list is empty.");
}
Node temp = first;
int ctr = 0;
while (temp != null) {
if (temp.item == item) {
l.last.next = temp;
l.last = last;
l.size = l.size + (size - ctr); // ------> Will need to deep dive this a bit.
return;
}
temp = temp.next;
ctr++;
}
throw new IllegalArgumentException("The input item is invalid.");
}
public void displayList() {
Node tempFirst = first;
while (tempFirst != null) {
System.out.print(tempFirst.item + " ");
tempFirst = tempFirst.next;
}
}
private static class Node {
int item;
Node next;
Node(int element, Node next) {
this.item = element;
this.next = next;
}
}
public int size() {
return size;
}
private Node hop(Interserction l, int hop) {
assert l != null;
assert l.first != null;
Node temp = l.first;
int counter = 0;
while (counter < hop) {
temp = temp.next;
counter++;
}
return temp;
}
private Node getIntersectionNode(Node node1, Node node2) {
assert node1 != null;
assert node2 != null;
while (node1 != node2) {
node1 = node1.next;
node2 = node2.next;
}
return node1;
}
private void verify(Interserction l) {
if (l == null) {
throw new NullPointerException("The input is null");
}
if (last == null) {
throw new NoSuchElementException("this object has null node");
}
if (l.last == null) {
throw new NoSuchElementException("The input object has null node");
}
}
public boolean doesIntersect(Interserction l) {
verify(l);
return last == l.last;
}
/**
* Similar to String.compareTo line 1137.
* Not using a function to get size for l.
* this is again similar to anotherString.value.length in compareToFunction
*/
public int findIntersectionItem(Interserction l) {
verify(l);
/**
* QQ: calling doesIntersect:
* pro: code duplication prevented, eg: last == l.last is not seen in 2 places
* con: exception check is redundant.
* Whats the right thing.
*
*/
if (!doesIntersect(l)) {
/**
* QQ: Verify this patten of state check function doesIntersect followed by an exception.
*/
throw new IllegalArgumentException("Input linkedlist does not intersect.");
}
Node intersect;
// guard clause just dint feel correct here.
if (l.size > size) {
Node begin = hop(l, l.size - size);
intersect = getIntersectionNode(first, begin);
} else {
Node begin = hop(this, size - l.size);
intersect = getIntersectionNode(begin, l.first);
}
// preferred single point of return.
return intersect.item;
}
public static void main(String[] args) {
Interserction i1 = new Interserction();
int[] l1 = {10, 20, 30, 40, 50, 60};
for (int i : l1) {
i1.add(i);
}
Interserction i2 = new Interserction();
int[] l2 = {17, 18};
for (int i : l2) {
i2.add(i);
}
i1.attach(i2, 30);
// testing same length.
System.out.println("Expted true, Actual: " + i1.doesIntersect(i2));
System.out.println("Expected 30, Actual: " + i1.findIntersectionItem(i2));
i1.displayList();
System.out.println();
i2.displayList();
System.out.println();
Interserction i3 = new Interserction();
int[] l3 = {18};
for (int i : l3) {
i3.add(i);
}
i1.attach(i3, 30);
// testing same length.
System.out.println("Expted true, Actual: " + i1.doesIntersect(i2));
System.out.println("Expected 30, Actual: " + i1.findIntersectionItem(i3));
i1.displayList();
System.out.println();
i3.displayList();
System.out.println();
}
}