Java实现链表的常见操作算法(2)

// 去掉重复元素
    private void distinctLink() {
        Hashtable<Integer, Integer> map = new Hashtable<Integer, Integer>();
        Node curNode = head;
        Node preNode = null;
        while (curNode != null) {
            if (map.containsKey(curNode.getData())) {
                preNode.setData(curNode.getData());
                preNode.setNext(curNode.getNext());
            } else {
                map.put(curNode.getData(), 1);
                preNode = curNode;
            }
            curNode = curNode.getNext();
        }
    }

// 返回倒数第k个结点,定义两个指针,第一个指针向前移动K-1次,之后两个指针同时前进,
    // 当第一个指针到达末尾时,第二个指针所在的位置即为倒数第k个结点
    private Node getReverNode(int k) {
        if (k < 1) {
            return null;
        }
        Node first = head;
        Node second = head;
        for (int i = 0; i < k - 1; i++) {
            first = first.getNext();
        }
        while (first.getNext() != null) {
            first = first.getNext();
            second = second.getNext();
        }
        return second;
    }

// 反转链表
    private void reserveLink() {
        Node preNode = null;
        Node curNode = head;
        Node tempNode = null;
        while (curNode != null) {
            tempNode = curNode.getNext();
            curNode.setNext(preNode);
            preNode = curNode;
            curNode = tempNode;
        }
        head = preNode;
    }

// 寻找链表的中间结点
    private Node getMiddleNode() {
        Node slowNode = head;
        Node quickNode = head;
        while (slowNode.getNext() != null && quickNode.getNext() != null) {
            slowNode = slowNode.getNext();
            quickNode = quickNode.getNext().getNext();
        }
        return slowNode;
    }

// 判断链表是否有环
    private boolean isRinged() {
        if (head == null) {
            return false;
        }
        Node slowNode = head;
        Node quickNode = head;
        while (slowNode.getNext() != null && quickNode.getNext() != null) {
            slowNode = slowNode.getNext();
            quickNode = quickNode.getNext().getNext();
            if (slowNode.getData() == quickNode.getData()) {
                return true;
            }
        }
        return false;
    }