摘要：愛寫設計鏈表的實現。單鏈表中的節點應該具有兩個屬性和。插入后，新節點將成為鏈表的第一個節點。將值為的節點追加到鏈表的最后一個元素。如果等于鏈表的長度，則該節點將附加到鏈表的末尾。如果索引有效，則刪除鏈表中的第個節點。操作次數將在之內。

愛寫bug (ID:iCodeBugs)

設計鏈表的實現。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節點應該具有兩個屬性：val 和 next。val 是當前節點的值，next 是指向下一個節點的指針/引用。如果要使用雙向鏈表，則還需要一個屬性 prev 以指示鏈表中的上一個節點。假設鏈表中的所有節點都是 0-index 的。

在鏈表類中實現這些功能：

get(index)：獲取鏈表中第 index 個節點的值。如果索引無效，則返回-1。

addAtHead(val)：在鏈表的第一個元素之前添加一個值為 val 的節點。插入后，新節點將成為鏈表的第一個節點。

addAtTail(val)：將值為 val 的節點追加到鏈表的最后一個元素。

addAtIndex(index,val)：在鏈表中的第 index 個節點之前添加值為 val 的節點。如果 index 等于鏈表的長度，則該節點將附加到鏈表的末尾。如果 index 大于鏈表長度，則不會插入節點。

deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個節點。

Design your implementation of the linked list. You can choose to use the singly linked list or the doubly linked list. A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node. If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement these functions in your linked list class:

get(index) : Get the value of the index-th node in the linked list. If the index is invalid, return -1.

addAtHead(val) : Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.

addAtTail(val) : Append a node of value val to the last element of the linked list.

addAtIndex(index, val) : Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.

deleteAtIndex(index) : Delete the index-th node in the linked list, if the index is valid.

示例：

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

提示：

所有值都在 [1, 1000] 之內。

操作次數將在 [1, 1000] 之內。

請不要使用內置的 LinkedList 庫。

先看圖解：

單鏈表添加操作

如果我們想在給定的結點 prev 之后添加新值，我們應該：

使用給定值初始化新結點 cur；

將 cur 的“next”字段鏈接到 prev 的下一個結點 next；

將 prev 中的“next”字段鏈接到 cur 。

刪除第一個結點

如果我們想刪除第一個結點，策略會有所不同。

正如之前所提到的，我們使用頭結點 head 來表示鏈表。我們的頭是下面示例中的黑色結點 23。

如果想要刪除第一個結點，我們可以簡單地將下一個結點分配給 head。也就是說，刪除之后我們的頭將會是結點 6。

鏈表從頭結點開始，因此結點 23 不再在我們的鏈表中。

圖片來源于LeetCode中國官網

高級程序設計語言中一般都有內置鏈表，這道題就是讓復現鏈表，看到有很多是用ArrayList、List等數據結構解的，很搞笑，題目說不能使用 LinkedList 庫，但 LinkedList 是繼承的ArrayList、List，，直接用這兩個庫一點意義都沒有。其實理解一下鏈表原理就好，高級語言都封裝好了鏈表，如果項目真的到了需要改寫鏈表底層結構來優化性能的那一步，那時候在實踐中基本已經摸清了這些東西。

class Node {//定義Node
    int val;
    Node next;

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

class MyLinkedList {

    Node head;//頭
    Node tail;//尾
    int size = 0;//鏈表長度

    public MyLinkedList() {//初始化數據
        head = new Node(0);//為了方便初始化一個本不存在的head，值為0
        tail = head;//初始下尾也指向和頭同一個對象
        size = 0;
    }

    public int get(int index) {
        if (index >= size || index < 0) {//index不在查找區間返回-1
            return -1;
        }
        Node cur = head;
        for (int i = 0; i <= index; i++) {//從head一個一個向下遍歷，到index
            cur = cur.next;
        }
        return cur.val;//返回值
    }

    public void addAtHead(int val) {
        Node temp = head.next;//temp對象是真實鏈表的第一個節點（因為head一直是初始化的 0 ）
        head.next = new Node(val);//構造的虛擬節點head的下一個節點指向新插入的節點
        head.next.next = temp;//新插入節點指向原本第一個真實節點
        size++;//計數
        if (size == 1) {
            tail = head.next;//如果只有一個節點此時尾節點也指向新加入的節點
        }
    }

    public void addAtTail(int val) {//添加尾節點
        tail.next = new Node(val);//把尾節點下一個對象指向新加入節點即可
        tail = tail.next;//刷新尾節點為新加入的節點
        size++;
    }

    public void addAtIndex(int index, int val) {
        if (index > size) {//插入值不在范圍直接返回。
            return;
        }
        Node cur = head;//當前節點從頭節點開始
        for (int i = 0; i < index; i++) {//遍歷到 插入位置的前一個節點 因為要求是插入到index的前面
            cur = cur.next;
        }
        Node temp = cur.next;//暫存當前節點的下一個節點
        cur.next = new Node(val);//把當前節點下一個對象指向新節點
        if (index == size) {
            tail = cur.next;//如果插入位置剛好是最后一個則把尾節點指向新加入節點
        }
        cur.next.next = temp;//新節點的下一個節點指向暫存節點位置
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index >= size || index < 0) {
            return;
        }
        Node cur = head;//從頭節點遍歷到index目標節點的前一個節點 因為要刪除目標節點
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        cur.next = cur.next.next;//目標節點前一個節點的下一個節點指向目標節點的下一個節點
        size--;//刷新節點數量
        if (cur.next == null) {
            tail = cur;
        }
    }
}

class Node:
    def __init__(self, val, _next=None):
        self.next = _next
        self.val = val


class MyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def get(self, index: int) -> int:
        if index > self.size - 1 or index < 0:
            return -1
        node = self.head
        for i in range(index):
            node = node.next
        return node.val

    def addAtHead(self, val: int) -> None:
        node = Node(val, self.head)
        self.head = node
        if self.size == 0:
            self.tail = node
        self.size = self.size + 1

    def addAtTail(self, val: int) -> None:
        node = Node(val)
        if self.size == 0:
            self.head = self.tail = node  # 原鏈表為空時，添加新節點后，更新鏈表的頭指針和尾指針為新增節點。
        else:
            self.tail.next = node  # 原鏈表不為空時，使原尾指針指向新節點，即可將新節點添加至原鏈表尾部
            self.tail = node  # 更新尾指針
        self.size = self.size + 1  # 更新此時鏈表的長度

    def addAtIndex(self, index: int, val: int) -> None:
        node = Node(val)
        if index > self.size:
            return
        if index <= 0:
            return self.addAtHead(val)  # index 小于等于0都默認為頭指針后添加節點

        if index == self.size:  # 如果index等于鏈表的長度添加尾指針后添加節點
            return self.addAtTail(val)
        prev = self.head  # 第一個節點對象開始遍歷
        for i in range(index - 1):
            prev = prev.next
        temp = prev.next
        prev.next = node
        node.next = temp
        self.size = self.size + 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        prev = self.head
        if index == 0:
            self.head = self.head.next
            self.size = self.size - 1
            return
        for i in range(index - 1):
            prev = prev.next
        if index == self.size - 1:
            self.tail = prev
        prev.next = prev.next.next
        self.size = self.size - 1

公眾號：愛寫bug (ID:iCodeBugs)