Skip to content

Instantly share code, notes, and snippets.

@Lucas-Kohorst
Last active October 18, 2019 13:42
Show Gist options
  • Save Lucas-Kohorst/3caa730a2dde241a6795c5ec32c81d9e to your computer and use it in GitHub Desktop.
Save Lucas-Kohorst/3caa730a2dde241a6795c5ec32c81d9e to your computer and use it in GitHub Desktop.
Intersection of nodes in linked lists
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class LList {
/**
* Default Constructor
*/
public LList() {
createNodes();
}
/**
* Creation of the Linked Lists
*/
public void createNodes() {
// Creating the shared "LESS" nodes
Node sharedS1Node = new Node('s', null);
Node sharedS2Node = new Node('s', sharedS1Node);
Node sharedENode = new Node('e', sharedS2Node);
Node sharedLNode = new Node('l', sharedENode);
// Creating chain A
Node chainADNode = new Node('d', sharedLNode);
Node chainANNode = new Node('n', chainADNode);
Node chainAENode = new Node('e', chainANNode);
// Setting headA
Node headA = new Node(chainAENode);
// Creating chain B
Node chainBTNode = new Node('t', sharedLNode);
Node chainBRNode = new Node('r', chainBTNode);
Node chainBONode = new Node('o', chainBRNode);
Node chainBF1Node = new Node('f', chainBONode);
Node chainBF2Node = new Node('f', chainBF1Node);
Node chainBENode = new Node('e', chainBF2Node);
// Setting headB
Node headB = new Node(chainBENode);
// Creating chain C
Node chainCHNode = new Node('h', sharedENode);
Node chainCCNode = new Node('c', chainCHNode);
// Setting headC
Node headC = new Node(chainCCNode);
findIntersection(headA, headB, headC);
}
/**
* Iterate over a Linked List and place each node into an array
* @param head, the pointer of the Linked List to put into a Array
* @return returnArray, the array of Nodes
*/
public List<Node> iterateLL(Node head) {
List<Node> returnArray = new ArrayList<Node>();
Node node = head.getNext();
while (node != null) {
returnArray.add(node);
node = node.getNext();
}
return returnArray;
}
/**
* Sort a list by it's address in memory
* @param list the list to sort
* @return the sorted list
*/
public List<Node> sortArrayByHashCode(List<Node> list) {
Collections.sort(list, new Comparator<Node>() {
public int compare(Node a, Node b) {
int value = a.compareTo(b);
if (value == 0) {
return value;
}
return a.hashCode() > b.hashCode() ? 1 : -1;
}
});
return list;
}
/**
* Find the intersection of three linked lists,
* solved by using the algorithm to find common numbers in
* three arrays from previous homework
* @param headA, the pointer of head A
* @param headB, the pointer of head B
* @param headC, the pointer of head C
*/
public void findIntersection(Node headA, Node headB, Node headC) {
// First iterate over the linked list and put it into a list
List<Node> arrA = iterateLL(headA);
List<Node> arrB = iterateLL(headB);
List<Node> arrC = iterateLL(headC);
// Array of the Nodes that Intersect
ArrayList<Node> arrIntersect = new ArrayList<Node>();
// Sorting the Lists
arrA = sortArrayByHashCode(arrA);
arrB = sortArrayByHashCode(arrB);
arrC = sortArrayByHashCode(arrC);
// Defining Counters
int counterA = 0;
int counterB = 0;
int counterC = 0;
// True if intersection was found
boolean intersection = false;
System.out.print("Lines intersect\nIntersection segment: ");
// Iterating over the size of all the lists to find equivalent values
while (counterA < arrA.size() && counterB < arrB.size() && counterC < arrC.size()) {
// First check if all of the Node values are equal
if (arrA.get(counterA) == arrB.get(counterB) && arrB.get(counterB) == arrC.get(counterC)) {
// If equal print out the value of the node then increment all the counters
System.out.print(arrA.get(counterA).getValue() + " ");
counterA++;
counterB++;
counterC++;
// Setting intersection to true
intersection = true;
}
// Check if the node in the A chain's memory value is less than the node in chain B
else if (arrA.get(counterA).hashCode() < arrB.get(counterB).hashCode()) {
// If it is increment the counter for A's chain
counterA++;
}
// Check if the node in the B chain's memory value is less than the node in chain C
else if (arrB.get(counterB).hashCode() < arrC.get(counterC).hashCode()) {
// If it is then increment the counter in B's chain
counterB++;
}
// Other wise chain C is not equal, increment it
else {
counterC++;
}
}
// Checking if intersection was found
if (!intersection) {
System.out.println("No intersection found");
}
System.out.println("\n");
}
/**
* Main Method
* @param args
*/
public static void main(String[] args) {
new LList();
}
}
class Node implements Comparable<Node> {
private char value;
private Node next;
public Node(char value, Node next) {
this.value = value;
this.next = next;
}
// For the pointers
public Node(Node next) {
this.next = next;
}
public void setValue(char value) {
this.value = value;
}
public void setNext(Node next) {
this.next = next;
}
public Node getNext() {
return next;
}
public char getValue() {
return value;
}
// Compare the memory location of the Nodes
public int compareTo(Node node) {
return this.hashCode() > node.hashCode() ? 1 : -1;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment