listAlgorithms/Algorithms.java

Go to the documentation of this file.

package listAlgorithms;

import java.util.HashSet;

public class Algorithms {

    private Algorithms() {
    }

    public static <T extends Comparable<T>> ListNode<T> buildList(T[] vals) {
        ListNode<T> head = null;
        ListNode<T> current = null;
        for (T val : vals) {
            ListNode<T> newNode = new ListNode<T>(val);
            if (head == null) {
                head = newNode;
                current = newNode;
            } else {
                current.setNext(newNode);
                current = newNode;
            }
        }
        return head;
    } // buildList

    public static <T extends Comparable<T>> boolean listEquals(ListNode<T> listA, ListNode<T> listB) {
        boolean equal = false;
        if ((listA != null) && (listB != null)) {
            equal = true;
            while ((listA.getNext() != null) && (listB.getNext() != null)) {
                if (listA.getValue().compareTo(listB.getValue()) != 0) {
                    equal = false;
                    break;
                }
                listA = listA.getNext();
                listB = listB.getNext();
            } // while
            if (equal
                    && ((listA.getNext() != null) || (listB.getNext() != null))) {
                equal = false;
            }
        }
        return equal;
    }

    public static <T extends Comparable<T>> ListNode<T> reverse(ListNode<T> head) {
        ListNode<T> newRoot = null;
        if (head != null) {
            ListNode<T> current = head;
            ListNode<T> t = null;

            while (current != null) {
                t = current.getNext();
                current.setNext(newRoot);
                newRoot = current;
                current = t;
            }
        }
        return newRoot;
    } // reverse

    public static <T extends Comparable<T>> void dedup(ListNode<T> head) {
        if (head != null) {
            HashSet<T> hash = new HashSet<T>();
            ListNode<T> trail = head;
            while (head != null) {
                T val = head.getValue();
                if (!hash.add(val)) { // add() returns true if the value was not
                                      // in the hash set
                    trail.setNext(head.getNext());
                } else {
                    trail = head;
                }
                head = head.getNext();
            }
        }
    } // dedup

    public static <T extends Comparable<T>> ListNode<T> kthFromEnd(ListNode<T> head, int k) {
        ListNode<T> kthNode = head;
        int cnt = 0;
        while (head.getNext() != null) {
            if (cnt >= k) {
                kthNode = kthNode.getNext();
            }
            cnt++;
            head = head.getNext();
        }
        if (cnt < k) {
            kthNode = null;
        }
        return kthNode;
    }

}