转载

循环链表的实现（Java）

循环链表，其实就是特殊的单链表。

单链表的尾结点指向 NULL，而循环链表的尾结点指向头结点，构成环状。

二、插入

循环链表的插入就是改变相邻结点指针的指向。时间复杂度为 O（1）。

和单链表的区别在于在循环链表末尾插入，新插入的节点需要指向头结点。

如图所示：

翻译成代码：

/**
     * 尾部插入
     *
     * @param newNode
     */
    public void insert(Node newNode) {
        if (head == null) {
            // 循环链表为空时，head 指向新的节点
            head = newNode;
        } else {
            Node temp = head;
            // 找到循环链表最后一个节点
            while (temp.next != head) {
                temp = temp.next;
            }
            // 插入新的节点
            temp.next = newNode;
        }
        // 循环链表新的结点指向 NULL
        newNode.next = head;
        // 循环链表长度加 1
        length++;
    }
复制代码

三、删除

循环链表的删除和插入一样，改变指针的转向就可以完成循环链表的删除操作，时间复杂度为 O（1）。

如图所示：

翻译为代码为：

/**
     * 删除数据域为指定值的元素
     *
     * @param e
     */
    public void del(int e) {
        Node temp = head;
        while (length >= 0) {
            // 找到数据域为 e 的结点
            if (temp.data == e) {
                if (temp.next == head) {
                    // 第一个节点
                    head = null;
                } else {
                    // 最后一个节点
                    temp.next = temp.next.next;
                }
                // 循环链表长度减 1
                length--;
                return;
            }
            // temp 后移          
            temp = temp.next;
        }
    }
复制代码

四、完整代码

/**
 * 循环链表的实现（特殊的单链表）
 *
 * @author liyanan
 * @date 2020/1/2 13:16
 */
public class CircleLinkedList {
    /**
     * 指向循环链表的第一个结点
     */
    private Node head;
    /**
     * 循环链表的长度
     */
    private int length;


    public CircleLinkedList() {
        head = null;
        length = 0;
    }

    public Node getHead() {
        return head;
    }

    public int getLength() {
        return length;
    }

    /**
     * 尾部插入
     *
     * @param newNode
     */
    public void insert(Node newNode) {
        if (head == null) {
            // 循环链表为空时，head 指向新的节点
            head = newNode;
        } else {
            Node temp = head;
            // 找到循环链表最后一个节点
            while (temp.next != head) {
                temp = temp.next;
            }
            // 插入新的节点
            temp.next = newNode;
        }
        // 循环链表新的结点指向 NULL
        newNode.next = head;
        // 循环链表长度加 1
        length++;
    }

    /**
     * 将新的结点插入到指定结点后
     *
     * @param preNode 指定节点
     * @param newNode 新的节点
     */
    public void insert(Node preNode, Node newNode) {
        newNode.next = preNode.next;
        preNode.next = newNode;
        length++;
    }

    /**
     * 删除数据域为指定值的元素
     *
     * @param e
     */
    public void del(int e) {
        Node temp = head;
        while (length >= 0) {
            // 找到数据域为 e 的结点
            if (temp.data == e) {
                if (temp.next == head) {
                    // 第一个节点
                    head = null;
                } else {
                    // 最后一个节点
                    temp.next = temp.next.next;
                }
                // 循环链表长度减 1
                length--;
                return;
            }
            // 找到下一个结点
            temp = temp.next;
        }
    }
    
    /**
     * 随机访问第 k 个结点
     *
     * @param k
     * @return
     */
    public Node find(int k) {
        if (k <= 0) {
            throw new RuntimeException("输入的参数 k 必须大于 0");
        }
        int cnt = 1;
        Node temp = head;
        // 找到第 k 个元素
        while (cnt != k) {
            temp = temp.next;
            cnt++;
        }
        return temp;
    }

    /**
     * 打印循环链表所有有效节点
     *
     * @return
     */
    public String printCircleLinkedList() {
        StringBuilder sb = new StringBuilder();
        int cnt = 0;
        Node temp = head;
        while (head != null && cnt < getLength()) {
            sb.append(temp.data);
            sb.append(" -> ");
            temp = temp.next;
            cnt++;
        }
        sb.append(", length = ");
        sb.append(length);
        return sb.toString();
    }
}

复制代码

原文 https://juejin.im/post/5e12a4946fb9a048116667f2

正文到此结束