侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【单链表】设计链表

GabrielxD
2022-04-30 / 0 评论 / 0 点赞 / 42 阅读 / 752 字 / 正在检测是否收录...

题目

707. 设计链表


设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:valnextval 是当前节点的值,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;
    }
};
0

评论区