JavaAlgorithms Elementary and no so elementary Java algorithms
listAlgorithms/Algorithms.java
Go to the documentation of this file.
```00001
00009 package listAlgorithms;
00010
00011 import java.util.HashSet;
00012
00023 public class Algorithms {
00024
00025     private Algorithms() {
00026     }
00027
00035     public static <T extends Comparable<T>> ListNode<T> buildList(T[] vals) {
00037         ListNode<T> current = null;
00038         for (T val : vals) {
00039             ListNode<T> newNode = new ListNode<T>(val);
00040             if (head == null) {
00042                 current = newNode;
00043             } else {
00044                 current.setNext(newNode);
00045                 current = newNode;
00046             }
00047         }
00049     } // buildList
00050
00059     public static <T extends Comparable<T>> boolean listEquals(ListNode<T> listA, ListNode<T> listB) {
00060         boolean equal = false;
00061         if ((listA != null) && (listB != null)) {
00062             equal = true;
00063             while ((listA.getNext() != null) && (listB.getNext() != null)) {
00064                 if (listA.getValue().compareTo(listB.getValue()) != 0) {
00065                     equal = false;
00066                     break;
00067                 }
00068                 listA = listA.getNext();
00069                 listB = listB.getNext();
00070             } // while
00071             if (equal
00072                     && ((listA.getNext() != null) || (listB.getNext() != null))) {
00073                 equal = false;
00074             }
00075         }
00076         return equal;
00077     }
00078
00096     public static <T extends Comparable<T>> ListNode<T> reverse(ListNode<T> head) {
00097         ListNode<T> newRoot = null;
00098         if (head != null) {
00100             ListNode<T> t = null;
00101
00102             while (current != null) {
00103                 t = current.getNext();
00104                 current.setNext(newRoot);
00105                 newRoot = current;
00106                 current = t;
00107             }
00108         }
00109         return newRoot;
00110     } // reverse
00111
00117     public static <T extends Comparable<T>> void dedup(ListNode<T> head) {
00118         if (head != null) {
00119             HashSet<T> hash = new HashSet<T>();
00121             while (head != null) {
00123                 if (!hash.add(val)) { // add() returns true if the value was not
00124                                       // in the hash set
00126                 } else {
00128                 }
00130             }
00131         }
00132     } // dedup
00133
00144     public static <T extends Comparable<T>> ListNode<T> kthFromEnd(ListNode<T> head, int k) {
00146         int cnt = 0;
00147         while (head.getNext() != null) {
00148             if (cnt >= k) {
00149                 kthNode = kthNode.getNext();
00150             }
00151             cnt++;