🌕 707. 设计链表

难度： 🌕

问题描述

---

解法

class MyLinkedList {
    Node head; // 添加哨兵节点
    Node tail;
    int size;

    public MyLinkedList() {
        head = new Node(-1);
        tail = new Node(-1);
        head.next = tail;
        tail.pre = head;
        size = 0;
    }
    
    public int get(int index) {
        // 特殊情况特判
        if(index >= size || index < 0) {
            return -1;
        }
        Node pre = head;
        for(int i = 0; i < index; i ++) {
            pre = pre.next;
        }
        return pre.next.val;
    }
    
    public void addAtHead(int val) {
        Node node = new Node(val);
        Node next = head.next;
        head.next = node;
        node.pre = head;
        node.next = next;
        next.pre = node;
        size ++;
    }
    
    public void addAtTail(int val) {
        Node node = new Node(val);
        Node pre = tail.pre;
        pre.next = node;
        node.pre = pre;
        node.next = tail;
        tail.pre = node;
        size ++;
    }

    public void addAtIndex(int index, int val) {
        // 特殊情况特判
        if(index > size) {
            return;
        }
        if(index < 0) {
            addAtHead(val);
            return;
        }
        if(index == size) {
            addAtTail(val);
            return;
        }
        // 定位到要插入的节点位置
        Node pre = head;
        for(int i = 0; i < index; i ++) {
            pre = pre.next;
        }
        // 在 pre 后面插入节点
        Node node = new Node(val);
        Node next = pre.next;
        pre.next = node;
        node.pre = pre;
        node.next = next;
        next.pre = node;
        size ++;
    }
    
    public void deleteAtIndex(int index) {
        // 特殊情况特判
        if(index >= size || index < 0) {
            return;
        }
        // 定位到要删除节点的位置
        Node pre = head;
        for(int i = 0; i < index; i ++) {
            pre = pre.next;
        }
        // 删除 pre 后面的节点
        Node next = pre.next.next;
        pre.next = next;
        next.pre = pre;
        size --;
    }
}

// 构造双向链表
class Node {
    int val;
    Node pre;
    Node next;
    Node(int val) {
        this.val = val;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

---

输出