1 leetcode707 设计链表

题目链接

重点：

• 创建虚拟头部head=Node(0)
• 增删时注意各个变量名的含义
• 增删循环结束后得到两个实例，分别是要打断的部分及后续以及后续
• 查找的时候如果范围是range(index+1)，因为有head，返回值为最后得到的node.next.value，如果范围是range(index+2)，返回值node.value

2 python代码（附解析）

# 单链表1.0

# 先定义一个Node
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# 再定义一个自己的链表
class MyLinkedList:

    def __init__(self):
        self.head = Node(0)  # 创建虚拟的头部
        self.count = 0  # 用来记录添加的节点数

    def get(self, index: int) -> int:
        if index >= 0 and index < self.count:  # 确保索引合法
            node = self.head  # 继承当前链表的状态
            for _ in range(index + 1):
                node = node.next
            return node.value
        else:
            return -1

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)  # 这就是创建虚拟头部的好处

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.count, val)


    def addAtIndex(self, index: int, val: int) -> None:  # 先写这个函数
        # 下面这两个if是对传入的index先进行一个预处理，处理两个特殊情况
        if index < 0:
            index = 0  # 如果传入一个小于0的索引，意味着这个值要添加到头部
        elif index > self.count:  # elif 选择执行，if if逐条执行
            return  # 如果 index 大于链表长度，则不会插入节点，直接返回

        # 预处理完index之后，开始进行正式的函数
        self.count += 1  # 成功调用一次这个函数，先计数器加一
        add_node = Node(val)  # 创建新加入的节点。等待后续往进添加

        # last_node就是创建一个None，用来准备接虚拟头部。cur_node就是虚拟头部，这里相当于每调用一次添加函数，都要重新更新一次链表（就是新创建一次）
        last_node, cur_node = None, self.head  # 上一个节点和当前的节点（准备计划被替换掉的节点），这里应该是只是初始化这两个定义，而不是真正的代表真实的这两个节点（不是这个意思，删除）
        # 但是为什么每次执行都要创建新的last和cur的情况下，还能保存原来的数据？？？？？
        # 解答：上面的cur_node=self.head 不是说创建cur为head（0）这个节点，而是说cur继承了该链表的整个当前的状态！！！！！！这就是为什么还能保留原来的数据
        # 确实，每次执行都要创建一个叫last的空玩意，和一个cur，但是这个cur可是继承了整个链表的当前状态的

        for _ in range(index + 1):  # 要遍历到该index，range（）不包括尾巴，所以到＋1
            last_node, cur_node = cur_node, cur_node.next  # 上一个节点（创建的空节点）承接当前虚拟头部节点，当前虚拟头部节点承接下一个节点
        else:
            last_node.next, add_node.next = add_node, cur_node


    def deleteAtIndex(self, index: int) -> None:
        if index >= 0 and index < self.count:  # 确认index合法
            self.count -= 1
            last_node, cur_node = None, self.head  # 创建一个空节点等着接后续，创建一个cur继承了当前的链表状态
            for _ in range(index + 1):
                last_node, cur_node = cur_node, cur_node.next  # 截止到最后一步，last是要删除打断的位置，cur是删除后要承接的后续
            else:
                last_node.next, cur_node.next = cur_node.next, None




# test
if __name__ == "__main__":
    linkedList = MyLinkedList()  # 这个命令执行完，就已经创建了一个列表，其中计数器为0，有个head，head是val为0，next为None的空Node

    linkedList.addAtHead(1)
    linkedList.addAtTail(3)
    linkedList.addAtIndex(1, 2)
    linkedList.get(1)
    linkedList.deleteAtIndex(1)
    linkedList.get(1)

3 代码图解

3.1 增加节点

3.2 删除节点

3.3 查询节点

3.4 其它