JavaAlgorithms
Elementary and no so elementary Java algorithms
|
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) { 00036 ListNode<T> head = null; 00037 ListNode<T> current = null; 00038 for (T val : vals) { 00039 ListNode<T> newNode = new ListNode<T>(val); 00040 if (head == null) { 00041 head = newNode; 00042 current = newNode; 00043 } else { 00044 current.setNext(newNode); 00045 current = newNode; 00046 } 00047 } 00048 return head; 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) { 00099 ListNode<T> current = head; 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>(); 00120 ListNode<T> trail = head; 00121 while (head != null) { 00122 T val = head.getValue(); 00123 if (!hash.add(val)) { // add() returns true if the value was not 00124 // in the hash set 00125 trail.setNext(head.getNext()); 00126 } else { 00127 trail = head; 00128 } 00129 head = head.getNext(); 00130 } 00131 } 00132 } // dedup 00133 00144 public static <T extends Comparable<T>> ListNode<T> kthFromEnd(ListNode<T> head, int k) { 00145 ListNode<T> kthNode = head; 00146 int cnt = 0; 00147 while (head.getNext() != null) { 00148 if (cnt >= k) { 00149 kthNode = kthNode.getNext(); 00150 } 00151 cnt++; 00152 head = head.getNext(); 00153 } 00154 if (cnt < k) { 00155 kthNode = null; 00156 } 00157 return kthNode; 00158 } 00159 00160 }