【单链表】设计链表

题目

707. 设计链表

---

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果 index 小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

示例 1：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

提示：

• 所有val值都在 [1, 1000] 之内。
• 操作次数将在 [1, 1000] 之内。
• 请不要使用内置的 LinkedList 库。

解题

方法一：单链表

思路

根据题意实现一个单链表即可，其中 addAtHead() 和 addAtTail() 方法可以直接调用 addAtIndex

代码

class MyLinkedList {
    int size;
    MyListNode dummy;

    public MyLinkedList() {
        size = 0;
        dummy = new MyListNode(-1);
    }
    
    public int get(int index) {
        return index < 0 || index >= size ? -1 : getNode(index).val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }

        MyListNode pred = getNode(Math.max(0, index) - 1);
        size++;
        pred.next = new MyListNode(val, pred.next);
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }

        MyListNode pred = getNode(Math.max(0, index) - 1);
        size--;
        pred.next = pred.next.next;
    }

    public MyListNode getNode(int index) {
        MyListNode target = dummy;
        for (int i = 0; i <= index; i++, target = target.next) { }
        return target;
    }
}

class MyListNode {
    int val;
    MyListNode next;

    public MyListNode() { }

    public MyListNode(int val) {
        this.val = val;
    }

    public MyListNode(int val, MyListNode next) {
        this.val = val;
        this.next = next;
    }
}

class MyLinkedList {
    struct MyListNode {
        int val;
        MyListNode* next;

        MyListNode() { }

        MyListNode(int val) : val(val) { }

        MyListNode(int val, MyListNode* next) : val(val), next(next) { }
    } * dummy;
    int size;

public:
    MyLinkedList() : dummy(new MyListNode()), size(0) { }
    
    int get(int index) {
        return index < 0 || index >= size ? -1 : getNode(index)->val;
    }
    
    void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        MyListNode* pred = getNode(index - 1);
        pred->next = new MyListNode(val, pred->next);
        ++size;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        MyListNode* pred = getNode(index - 1);
        pred->next = pred->next->next;
        --size;
    }

    MyListNode* getNode(int index) {
        MyListNode* target = dummy;
        for (int i = 0; i <= index; i++, target = target->next) { }
        return target;
    }
};