707. 设计链表

707. 设计链表

题解

class MyLinkedList {
    /**
     * 伪头节点
     */
    private ListNode dummyHead;
    private ListNode tail;
    private int size;
    public static class ListNode {
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public MyLinkedList() {
        dummyHead = new ListNode(0);
        tail = dummyHead;
        size = 0;
    }
    /**
     * 根据索引获取节点值
     *
     * @param index
     * @return
     */
    public int get(int index) {
        ListNode node = getNode(index);
        if (node == null) {
            return -1;
        } else {
            return node.val;
        }
    }
    /**
     * 私有辅助方法，根据索引获取节点
     *
     * @param index
     * @return
     */
    private ListNode getNode(int index) {
        if (index < 0 || index > size - 1) return null;
        ListNode temp = dummyHead.next;
        for (int i = 0; i < index && temp != null; i++) {
            temp = temp.next;
        }
        return temp;
    }
    /**
     * 在头部插入元素
     *
     * @param val
     */
    public void addAtHead(int val) {
        // 生成一个结点，存放的值为 val
        ListNode addNode = new ListNode(val);
        // 注意动静结合原则，添加结点时，注意修改 tail 指针
        if (dummyHead == tail) tail = addNode;
        ListNode tempHead = dummyHead.next;
        dummyHead.next = addNode;
        addNode.next = tempHead;
        size ++;
    }
    /**
     * 在尾部插入元素
     *
     * @param val
     */
    public void addAtTail(int val) {
        tail.next = new ListNode(val);
        tail = tail.next;
        size ++;
    }
    /**
     * 在索引 index 处插入元素
     *
     * @param index
     * @param val
     */
    public void addAtIndex(int index, int val) {
        if (index <= 0) {
            // 如果 index 小于 0，则在头部插入结点
            addAtHead(val);
        } else if (index > size) {
            // 如果 index 大于链表长度，则不会插入结点
        } else if (index == size) {
            // 如果 index 等于链表的长度，则该结点将附加到链表的末尾
            addAtTail(val);
        } else {
            ListNode nodeWithPreIndex = getNode(index - 1);
            ListNode tempNext = nodeWithPreIndex.next;
            nodeWithPreIndex.next = new ListNode(val);
            nodeWithPreIndex.next.next = tempNext;
            size ++;
        }
    }
    /**
     * 删除索引为 index 的元素
     *
     * @param index
     */
    public void deleteAtIndex(int index) {
        // 如果index无效，那么什么也不做
        if (index < 0 || index > size - 1) return;
        // 找到index前面的结点
        ListNode temp = dummyHead;
        for (int i = 0; i < index && temp != null; i++) {
            temp = temp.next;
        }
        // 如果要删除的是最后一个结点，那么需要更改tail指针
        if (temp.next == tail) {
            tail = temp;
        }
        // 执行删除
        temp.next = temp.next.next;
        size--;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        ListNode listNode = dummyHead.next;
        sb.append("size: ").append(size).append(" ; ");
        while (listNode != null) {
            sb.append(listNode.val).append("->");
            listNode = listNode.next;
        }
        sb.append("NULL");
        return sb.toString();
    }
}