摘要：愛寫設(shè)計(jì)鏈表的實(shí)現(xiàn)。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性和。插入后，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)。將值為的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素。如果等于鏈表的長度，則該節(jié)點(diǎn)將附加到鏈表的末尾。如果索引有效，則刪除鏈表中的第個(gè)節(jié)點(diǎn)。操作次數(shù)將在之內(nèi)。

愛寫bug (ID:iCodeBugs)

設(shè)計(jì)鏈表的實(shí)現(xiàn)。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性：val 和 next。val 是當(dāng)前節(jié)點(diǎn)的值，next 是指向下一個(gè)節(jié)點(diǎn)的指針/引用。如果要使用雙向鏈表，則還需要一個(gè)屬性 prev 以指示鏈表中的上一個(gè)節(jié)點(diǎn)。假設(shè)鏈表中的所有節(jié)點(diǎn)都是 0-index 的。

在鏈表類中實(shí)現(xiàn)這些功能：

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

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

addAtTail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素。

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

deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個(gè)節(jié)點(diǎn)。

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);   //鏈表變?yōu)?-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //現(xiàn)在鏈表是1-> 3
linkedList.get(1);            //返回3

提示：

所有值都在 [1, 1000] 之內(nèi)。

操作次數(shù)將在 [1, 1000] 之內(nèi)。

請(qǐng)不要使用內(nèi)置的 LinkedList 庫。

先看圖解：

單鏈表添加操作

如果我們想在給定的結(jié)點(diǎn) prev 之后添加新值，我們應(yīng)該：

使用給定值初始化新結(jié)點(diǎn) cur；

將 cur 的“next”字段鏈接到 prev 的下一個(gè)結(jié)點(diǎn) next；

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

刪除第一個(gè)結(jié)點(diǎn)

如果我們想刪除第一個(gè)結(jié)點(diǎn)，策略會(huì)有所不同。

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

如果想要?jiǎng)h除第一個(gè)結(jié)點(diǎn)，我們可以簡單地將下一個(gè)結(jié)點(diǎn)分配給 head。也就是說，刪除之后我們的頭將會(huì)是結(jié)點(diǎn) 6。

鏈表從頭結(jié)點(diǎn)開始，因此結(jié)點(diǎn) 23 不再在我們的鏈表中。

圖片來源于LeetCode中國官網(wǎng)

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

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() {//初始化數(shù)據(jù)
        head = new Node(0);//為了方便初始化一個(gè)本不存在的head，值為0
        tail = head;//初始下尾也指向和頭同一個(gè)對(duì)象
        size = 0;
    }

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

    public void addAtHead(int val) {
        Node temp = head.next;//temp對(duì)象是真實(shí)鏈表的第一個(gè)節(jié)點(diǎn)（因?yàn)閔ead一直是初始化的 0 ）
        head.next = new Node(val);//構(gòu)造的虛擬節(jié)點(diǎn)head的下一個(gè)節(jié)點(diǎn)指向新插入的節(jié)點(diǎn)
        head.next.next = temp;//新插入節(jié)點(diǎn)指向原本第一個(gè)真實(shí)節(jié)點(diǎn)
        size++;//計(jì)數(shù)
        if (size == 1) {
            tail = head.next;//如果只有一個(gè)節(jié)點(diǎn)此時(shí)尾節(jié)點(diǎn)也指向新加入的節(jié)點(diǎn)
        }
    }

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

    public void addAtIndex(int index, int val) {
        if (index > size) {//插入值不在范圍直接返回。
            return;
        }
        Node cur = head;//當(dāng)前節(jié)點(diǎn)從頭節(jié)點(diǎn)開始
        for (int i = 0; i < index; i++) {//遍歷到 插入位置的前一個(gè)節(jié)點(diǎn) 因?yàn)橐笫遣迦氲絠ndex的前面
            cur = cur.next;
        }
        Node temp = cur.next;//暫存當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
        cur.next = new Node(val);//把當(dāng)前節(jié)點(diǎn)下一個(gè)對(duì)象指向新節(jié)點(diǎn)
        if (index == size) {
            tail = cur.next;//如果插入位置剛好是最后一個(gè)則把尾節(jié)點(diǎn)指向新加入節(jié)點(diǎn)
        }
        cur.next.next = temp;//新節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向暫存節(jié)點(diǎn)位置
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index >= size || index < 0) {
            return;
        }
        Node cur = head;//從頭節(jié)點(diǎn)遍歷到index目標(biāo)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) 因?yàn)橐獎(jiǎng)h除目標(biāo)節(jié)點(diǎn)
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        cur.next = cur.next.next;//目標(biāo)節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向目標(biāo)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
        size--;//刷新節(jié)點(diǎn)數(shù)量
        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  # 原鏈表為空時(shí)，添加新節(jié)點(diǎn)后，更新鏈表的頭指針和尾指針為新增節(jié)點(diǎn)。
        else:
            self.tail.next = node  # 原鏈表不為空時(shí)，使原尾指針指向新節(jié)點(diǎn)，即可將新節(jié)點(diǎn)添加至原鏈表尾部
            self.tail = node  # 更新尾指針
        self.size = self.size + 1  # 更新此時(shí)鏈表的長度

    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都默認(rèn)為頭指針后添加節(jié)點(diǎn)

        if index == self.size:  # 如果index等于鏈表的長度添加尾指針后添加節(jié)點(diǎn)
            return self.addAtTail(val)
        prev = self.head  # 第一個(gè)節(jié)點(diǎn)對(duì)象開始遍歷
        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

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