设计链表

难度: Medium

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示：

0 <= index, val <= 1000
请不要使用内置的 LinkedList 库。
调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

Submission

运行时间: 208 ms

内存: 15.8 MB

class ListNode:

    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class MyLinkedList:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dummy = ListNode()
        self.size = 0


    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 index >= self.size or index < 0:
            return -1

        p = self.dummy
        for _ in range(index+1):
            p = p.next
        return p.val


    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.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        """
        Append a node of value val to the last element of the linked list.
        """
        self.addAtIndex(self.size, 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 > self.size:
            return

        if index < 0:
            index = 0

        pre = self.dummy
        for _ in range(index):
            pre = pre.next

        node = ListNode(val)
        tmp = pre.next
        pre.next = node
        node.next = tmp
        self.size += 1

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

        p = self.dummy
        for _ in range(index):
            p = p.next

        p.next = p.next.next
        self.size -= 1

# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

Explain

此题解实现了一个基本的单链表结构。类 ListNode 定义了链表的节点，包含节点值和指向下一个节点的指针。MyLinkedList 类则提供了链表的各种操作。初始化时创建一个虚拟头节点（dummy node）来简化边界条件处理。增加、删除和获取节点时都是通过遍历到目标位置来完成相应的操作。addAtHead 和 addAtTail 是特殊情况的 addAtIndex，分别在头部和尾部插入节点。

时间复杂度: O(n)

空间复杂度: O(n)

class ListNode:

    def __init__(self, val=0, next=None):
        self.val = val  # 节点存储的数据
        self.next = next  # 指向下一个节点的指针


class MyLinkedList:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dummy = ListNode()  # 初始化一个虚拟头节点，简化边界处理
        self.size = 0  # 链表的当前大小


    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 index >= self.size or index < 0:
            return -1  # 索引无效时返回-1

        p = self.dummy
        for _ in range(index+1):
            p = p.next  # 遍历到目标节点
        return p.val  # 返回节点值


    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.addAtIndex(0, val)  # 在头部插入等同于在索引0处插入

    def addAtTail(self, val: int) -> None:
        \"\"\"
        Append a node of value val to the last element of the linked list.
        \"\"\"
        self.addAtIndex(self.size, 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 > self.size:
            return  # 索引大于链表长度，不进行插入

        if index < 0:
            index = 0  # 负索引处理为0

        pre = self.dummy
        for _ in range(index):
            pre = pre.next  # 找到插入点的前一个位置

        node = ListNode(val)
        tmp = pre.next
        pre.next = node
        node.next = tmp  # 插入新节点
        self.size += 1  # 更新链表大小

    def deleteAtIndex(self, index: int) -> None:
        \"\"\"
        Delete the index-th node in the linked list, if the index is valid.
        \"\"\"
        if index >= self.size or index < 0:
            return  # 索引无效，不进行删除

        p = self.dummy
        for _ in range(index):
            p = p.next  # 找到需要删除的节点的前一个节点

        p.next = p.next.next  # 删除节点
        self.size -= 1  # 更新链表大小

# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

Explore

使用虚拟头节点可以简化插入和删除操作的边界条件处理。当链表为空时，直接操作实际头节点会需要特别处理头节点的变化，例如，插入新节点时需要更新头节点，删除时可能导致头节点不存在。而使用虚拟头节点，无论链表是否为空，头节点的插入和删除操作都可以统一处理，不需要单独考虑头节点是否存在的问题，因此代码更简洁，且易于维护。

在`addAtIndex`方法中，如果`index`等于链表的当前长度，这表示插入的位置是在链表的末尾。这是一个有效的操作，因为它等同于`addAtTail`方法的功能。如果`index`大于链表的长度，则表示插入点在链表的范围之外，这种情况下插入操作无法进行，因为它不会与现有的任何节点相邻接。因此，只有当`index`大于链表长度时，插入操作才被视为无效，从而直接返回不执行插入。

在`deleteAtIndex`方法中，通过首先找到要删除的节点的前一个节点（称为`pre`），然后将`pre`的`next`指针更新为`pre.next.next`，实现删除操作。这种操作直接跳过了要删除的节点，将其从链表中移除，并且保持了前一个节点和后一个节点的正确连接。这样，除了被删除的节点外，所有其他节点依然保持正确的连接状态，确保链表的结构完整性。

在`addAtIndex`方法中，如果`index`为0或小于0，将在链表的开始位置插入新节点，这等同于调用`addAtHead`方法。如果`index`等于链表的当前长度，新节点将添加到链表的末尾，这与`addAtTail`方法的效果相同。在`deleteAtIndex`方法中，如果`index`为0，将删除链表的第一个实际节点，这需要特别处理虚拟头节点的`next`指针。对于插入和删除操作，通过调整`index`的值和检查`index`的有效性，可以很好地处理这些边界情况，确保操作的正确性。