问题说明（含示例）

问题描述：设计并实现一个单链表的类 MyLinkedList，支持以下操作：

• MyLinkedList()：初始化链表。
• get(index)：获取下标为 index 的节点值，若下标无效返回 -1。
• addAtHead(val)：在链表头部插入值为 val 的节点。
• addAtTail(val)：在链表尾部插入值为 val 的节点。
• addAtIndex(index, val)：在下标为 index 的节点前插入值为 val 的节点（若 index 等于链表长度则追加到尾部，若 index 大于长度则不插入）。
• deleteAtIndex(index)：若下标有效，删除下标为 index 的节点。

示例：输入操作序列：["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]输入参数：[[], [1], [3], [1, 2], [1], [1], [1]]

输出结果：[null, null, null, null, 2, null, 3]

解释：

1. 初始化链表 myLinkedList。
2. 头部插入 1 → 链表：1。
3. 尾部插入 3 → 链表：1->3。
4. 在 index=1 前插入 2 → 链表：1->2->3。
5. 获取 index=1 的值 → 返回 2。
6. 删除 index=1 的节点 → 链表：1->3。
7. 获取 index=1 的值 → 返回 3。

解题关键

核心思路是基于单链表的节点结构，通过维护头节点和链表长度，实现各操作的逻辑，具体步骤：

1. 节点定义：用 ListNode 类表示节点，包含 val（值）和 next（指向下一节点的引用）。
2. 链表初始化：维护 head（头节点）和 length（链表长度），初始时 head=None，length=0。
3. get 操作：
   • 先判断索引有效性（0 ≤ index < length），无效返回 -1。
   • 从 head 开始遍历 index 次，定位到目标节点并返回其值。
4. addAtHead 操作：
   • 创建新节点，新节点的 next 指向当前 head，再将 head 更新为新节点，长度 +1。
5. addAtTail 操作：
   • 若链表为空，直接将新节点作为 head；否则遍历到最后一个节点，将其 next 指向新节点，长度 +1。
6. addAtIndex 操作：
   • 若索引无效（index < 0 或 index > length），直接返回。
   • 若索引为 0，复用 addAtHead；否则遍历到 index-1 节点，插入新节点（新节点 next 指向原 index 节点，index-1 节点 next 指向新节点），长度 +1。
7. deleteAtIndex 操作：
   • 若索引无效（index < 0 或 index ≥ length），直接返回。
   • 若索引为 0，将 head 更新为 head.next；否则遍历到 index-1 节点，将其 next 指向 index 节点的下一节点（跳过 index 节点），长度 -1。

对应代码

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

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

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

    def addAtHead(self, val: int) -> None:
        new_node = ListNode(val)
        new_node.next = self.head
        self.head = new_node
        self.length += 1

    def addAtTail(self, val: int) -> None:
        new_node = ListNode(val)
        if self.length == 0:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        self.length += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.length:
            return
        if index == 0:
            self.addAtHead(val)
        else:
            new_node = ListNode(val)
            current = self.head
            for _ in range(index - 1):
                current = current.next
            new_node.next = current.next
            current.next = new_node
            self.length += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.length:
            return
        if index == 0:
            self.head = self.head.next
        else:
            current = self.head
            for _ in range(index - 1):
                current = current.next
            current.next = current.next.next
        self.length -= 1

对应的基础知识

实现该算法需掌握以下基础概念与操作：

1. 单链表结构：由节点组成，每个节点包含数据和指向下一节点的引用，逻辑上连续但物理上非连续。
2. 类与对象：用 ListNode 类定义节点结构，MyLinkedList 类封装链表操作，通过实例化对象管理链表。
3. 引用与指针：Python 中通过变量引用节点对象，next 属性存储对下一节点的引用，实现节点间的连接。
4. 循环遍历：通过 for 或 while 循环移动节点引用（如 current = current.next），实现对链表的访问。
5. 边界条件处理：判断索引是否有效（如 index < 0 或超出长度）、链表为空（head = None）等特殊情况。

对应的进阶知识

该问题的解决涉及数据结构与算法的进阶思想：

1. 时间复杂度分析：
   • get、addAtIndex、deleteAtIndex 需遍历到目标位置，时间复杂度为 O (n)（n 为链表长度）。
   • addAtHead 直接操作头节点，时间复杂度为 O (1)；addAtTail 在非空链表中需遍历到尾部，时间复杂度为 O (n)。
2. 空间复杂度：所有操作仅使用常数级额外空间（存储节点引用和临时变量），空间复杂度为 O (1)。
3. 数据结构选择：单链表适合频繁插入 / 删除操作（无需像数组那样移动元素），但随机访问效率较低（需从头遍历）。
4. 状态一致性维护：通过 length 变量实时记录链表长度，避免每次操作都遍历计数，优化效率；需确保 length 与实际节点数严格同步。

编程思维与启示

1. 抽象数据结构实现：将链表的底层细节（节点连接）封装在类方法中，对外提供简洁接口（如 get、add），体现封装思想。
2. 辅助变量的价值：length 变量看似简单，却能大幅简化索引有效性判断，避免冗余遍历，体现 “空间换时间” 的优化思路。
3. 边界情况优先考虑：链表操作中，空链表、头节点、尾节点的处理是易错点，需优先设计这些场景的逻辑（如 addAtTail 中先判断 length == 0）。
4. 引用操作的严谨性：单链表的核心是节点引用的修改（如 current.next = new_node），需明确变量指向的对象，避免因引用错误导致链表断裂（如 deleteAtIndex 中需修改前一节点的 next，而非局部变量 current）。