Daily LeetCode – day0056 0707. Design Linked List

// 0707. Design Linked List
class MyLinkedList {
    private Node head;
    private Node tail;
    private int size;

    public MyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    public int get(int index) {
        if (index < 0 || index >= this.size) return -1;
        Node curr = this.head;
        while (index > 0) {
            --index;
            curr = curr.next;
        }
        return curr.val;
    }

    public Node getNodeAt(int index) {
        Node curr = head;
        while (index > 0) {
            --index;
            curr = curr.next;
        }
        return curr;
    }

    public void addAtHead(int val) {
        Node node = new Node(val);
        if (this.size == 0) {
            this.head = node;
            this.tail = node;
        } else {
            node.next = this.head;
            this.head = node;
        }
        ++this.size;
    }

    public void addAtTail(int val) {
        Node node = new Node(val);
        if (this.size == 0) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            this.tail = node;
        }
        ++this.size;
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > this.size) return;
        if (index == 0) {
            addAtHead(val);
        } else if (index == this.size) {
            addAtTail(val);
        } else {
            Node previous = getNodeAt(index - 1);
            Node next = previous.next;
            Node curr = new Node(val);
            previous.next = curr;
            curr.next = next;
            ++this.size;
        }
    }

    public void deleteFirst() {
        if (this.size == 0) return;
        else if (this.size == 1) {
            this.head = null;
            this.tail = null;
        } else {
            Node curr = this.head;
            Node next = curr.next;
            curr.next = null;
            this.head = next;
        }
        --this.size;
    }

    public void deleteLast() {
        if (this.size == 0) return;
        else if (this.size == 1) {
            this.head = null;
            this.tail = null;
        } else {
            Node secondLast = getNodeAt(this.size - 2);
            secondLast.next = null;
            this.tail = secondLast;
        }
        this.size--;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= this.size) return;
        if (index == 0) {
            deleteFirst();
        } else if (index == this.size - 1) {
            deleteLast();
        } else {
            Node previous = getNodeAt(index - 1);
            Node curr = previous.next;
            previous.next = previous.next.next;
            --this.size;
        }
    }
}

class Node {
    Node next = null;
    int val = 0;

    public Node(int val) {
        this.val = val;
    }
}
学习笔记:
今天这是一道设计题。
设计链表,链表是个比较有逻辑的数据结构。
先看了老外的代码,借鉴了不少,还进行了优化改良。
这里其实一共8个函数:
根据下标得到值,
根据下标得到结点,(题目没要求)
在头上加结点,
在尾上加结点,
根据下标加结点,
在头上删结点,(题目没要求)
在尾上删结点,(题目没要求)
根据下标删结点。

没要求的都会在其他函数中用得上,所以也就有了。
暂时没有去考虑双向链表的话怎么写,以后有空了得写写看。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。