1.1.题目描述
你可以选择使用单链表或者双链表,设计并实现自己的链表。
单链表中的节点应该具备两个属性: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 的节点。
1.2.题目地址
https://leetcode.cn/problems/design-linked-list/description/
2.1.解题思路
双链表
2.2.解题步骤
第一步,定义节点,双链表节点结构有val、next、prev属性。
第二步,初始化链表,定义头部哑结点和尾部哑结点,并将两节点进行连接。
第三步,遍历链表index次,从head节点开始,可以获取index下标的节点,如果获取的节点为尾部哑结点,直接退出返回-1,因为超出范围了。
第四步,设计在头尾加节点,有dumbHead、dumbTail俩哑结点,这俩功能很容易就能实现。
第五步,从head开始遍历index次获取下标为index的节点,并在该节点的前面添加上新节点,如果获取到的节点为None,说明index超出范围了,不能添加,返回-1。
第六步,也是从head开始遍历index次获取需要删除的节点,然后删除,需要注意的是如果获取到的需要删除的节点是尾部哑结点,则不删除,因为此时索引超出范围了。
Python代码
4.执行结果