Last active
October 18, 2019 13:42
-
-
Save Lucas-Kohorst/3caa730a2dde241a6795c5ec32c81d9e to your computer and use it in GitHub Desktop.
Intersection of nodes in linked lists
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(); | |
} | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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