707. Design Linked List - Medium

前往題目

思路

這題就是實作linkedList，簡單但細節很多，很容易出錯

Code

class MyLinkedList {
    private class Node {
        Node next;
        int val;

        public Node(int val) {
            this.next = null;
            this.val = val;
        }
    }

    Node head;
    Node tail;
    int size;

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

    public int get(int index) {
        // Empty or index out of bound or invalid index
        if (size == 0 || index >= size || index < 0)
            return -1;

        // Get the node
        Node res = head;
        while (index > 0) {
            res = res.next;
            --index;
        }
        return res.val;
    }

    public void addAtHead(int val) {
        Node newHead = new Node(val);

        if (size == 0) {
            head = newHead;
            tail = head;
        } else {
            // Connect with the old head
            newHead.next = head;
            // Change the head
            head = newHead;
        }
        ++size;
    }

    public void addAtTail(int val) {
        Node newTail = new Node(val);

        if (size == 0) {
            head = newTail;
            tail = newTail;
        } else {
            // old tail -> newTail
            tail.next = newTail;
            // switch the tail to the latest tail
            tail = newTail;
        }
        ++size;
    }

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

        return cur;
    }

    public void addAtIndex(int index, int val) {
        // Index is invalid, treat it as 0
        if (index < 0)
            index = 0;
        // Index = the length of the list
        else if (index == size)
            addAtTail(val);
        // Index is greater than the length
        else if (index > size)
            return;
        // Index is 0, insert in the head
        else if (index == 0)
            addAtHead(val);
        else {
            Node prev = getNodeAt(index - 1);
            Node forward = prev.next;
            Node cur = new Node(val);
            prev.next = cur;
            cur.next = forward;

            ++size;
        }

    }

    public void deleteAtIndex(int index) {
        // Invalid index
        if (index < 0 || index >= size)
            return;

        // Delete the head
        if (index == 0) {
            deleteHead();
        } else if (index == size - 1) { // Delete the tail
            deleteTail();
        } else {
            Node prev = getNodeAt(index - 1);
            Node cur = prev.next;
            Node forward = prev.next.next;
            prev.next = forward; // Connect 1st and 3rd node
            cur.next = null; // Disconnect
            --size;
        }
    }

    private void deleteHead() {
        if (size == 0)
            return;
        else if (size == 1) {
            head = null;
            tail = null;
        } else {
            Node newHead = head.next;
            head.next = null; // Disconnect
            head = newHead;
        }
        --size;
    }

    private void deleteTail() {
        if (size == 0)
            return;
        else if (size == 1) {
            head = null;
            tail = null;
        } else {
            // Get the second last node
            Node secLast = getNodeAt(size - 2);
            // Disconnect the last node
            secLast.next = null;
            // Assign new tail
            tail = secLast;
        }
        --size;
    }
}