題目

難度：★★☆☆☆
類型：鏈表，設(shè)計(jì)題

設(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)。

解答

網(wǎng)上有很多針對這道題的解答，還有人吐槽這道題為什么被當(dāng)做難題來做。這里筆者使用python3中的列表實(shí)現(xiàn)題目中要求的鏈表。需要注意下標(biāo)越界時(shí)的處理，不然會(huì)有各種bug。

class MyLinkedList:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.linked_list = []

    def get(self, index: int) -> int:
        """
        Get the value of the index-th node in the linked list. If the index is invalid, return -1.
        """
        if 0 <= index <= len(self.linked_list) - 1:
            return self.linked_list[index]
        else:
            return -1

    def addAtHead(self, val: int) -> None:
        """
        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.
        """
        self.linked_list.insert(0, val)

    def addAtTail(self, val: int) -> None:
        """
        Append a node of value val to the last element of the linked list.
        """
        self.linked_list.append(val)

    def addAtIndex(self, index: int, val: int) -> None:
        """
        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.
        """
        if index <= len(self.linked_list):
            self.linked_list.insert(index, val)

    def deleteAtIndex(self, index: int) -> None:
        """
        Delete the index-th node in the linked list, if the index is valid.
        """
        if 0 <= index <= len(self.linked_list) - 1:
            return self.linked_list.pop(index)

如有疑問或建議，歡迎評論區(qū)留言~