上传了网站标志 功能链接,seo排名优化推广,网站建设业务方法,高中信息技术课程做网站LeetCode.707设计链表 1.问题描述2.解题思路3.代码 1.问题描述
你可以选择使用单链表或者双链表#xff0c;设计并实现自己的链表。
单链表中的节点应该具备两个属性#xff1a;val 和 next 。val 是当前节点的值#xff0c;next 是指向下一个节点的指针/引用。
如果是双… LeetCode.707设计链表 1.问题描述2.解题思路3.代码 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 的节点。
示例
输入
[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 。
2.解题思路
使用虚拟头结点这道题目设计链表的五个接口 获取链表第index个节点的数值先判断index是否合法index 0 || index (size - 1)便不合法。定义一个指针遍历如果直接操作头结点头结点值被改了无法返回头结点。 ListNode* cur dummyHead-next;
while(index) {cur cur-next;index--;
}
return cur-val;为何临时指针指针指向dummyHead-next以及循环如何写可带入一个节点进行验证。如果index0那么相当于获得原始头结点的值while循环直接跳过之后return确实合理那么while循环以及临时指针的指向便没问题。 在链表的最前面插入一个节点在虚拟头结点和头结点之间插入新节点就好了 newNode-next dummyHead-next;
dummyHead-next newNode;注意以上顺序不可变 在链表的最后面插入一个节点cur节点必须指向最后一个节点。怎么找尾结点 while(cur-next ! nullptr) {cur cur-next; //只要不为空就一直执行这句话
}在链表第index个节点前面插入一个节点 如果要在第index个节点钱插入必须保证第index个节点为cur-next,也就是cur指向第index个节点的前一位。只有知道操作节点的前一个节点才能进行后续操作。 ListNode* cur dummyHead;
while(index) {cur cur-next;index--;
}
newNode-next cur-next;
cur-next newNode;
size;检验对否可随便代入一个节点便知道。如果index0那么while循环不操作等等进行分析。 删除链表的第index个节点 同理删除第index个节点必须知道前一个节点的指针。必须保证第index个节点为cur-next ListNode* cur dummyHead;
while(index) {cur cur-next;index--;
}
ListNode* tmp cur-next;
cur-next cur-next-next;
delete tmp;
tmp nullptr;
size--;delete命令指示释放了tmp指针原本所指的那部分内存被delete后的指针tmp的值地址并非就是NULL而是随机值。也就是被delete后如果不再加上一句tmpnullptr,tmp会成为乱指的野指针,如果之后的程序不小心使用了tmp会指向难以预想的内存空间。
3.代码
C
class MyLinkedList {public:struct ListNode {int val;ListNode* next;ListNode(int x): val(x), next(NULL) {}//构造函数};MyLinkedList() {dummyHead new ListNode(0); // 虚拟头节点size 0;// 初始化单链表长度}// 获取链表中第 index个节点的值:// 获取到第index个节点数值如果index是非法数值直接返回-1// 注意index是从0开始的第0个节点就是头结点int get(int index) {if(index 0 || index (size - 1)) { // 如果 index 不合理返回 -1return -1;}ListNode* cur dummyHead-next; //创建一个指针 cur指向虚拟头结点的下一个节点。//循环遍历链表移动 cur 指针到第 index 个节点处。while(index) {cur cur-next;index--;}return cur-val;}//在链表头部插入新节点void addAtHead(int val) {//创建一个新节点ListNode* newNode new ListNode(val);//注意以下两句话的顺序newNode-next dummyHead-next;dummyHead-next newNode;// 链表大小加1。size;}//在链表尾部添加新节点void addAtTail(int val) {//创建一个新节点ListNode* newNode new ListNode(val);//创建一个指针 cur指向虚拟头结点ListNode* cur dummyHead;//循环遍历链表移动 cur 指针到最后一个节点处while(cur-next ! nullptr) {cur cur-next;}//将最后一个节点的下一个节点指向新节点。cur-next newNode;size;}//在指定位置插入新节点// 在第index个节点之前插入一个新节点例如index为0那么新插入的节点为链表的新头节点。// 如果index 等于链表的长度则说明是新插入的节点为链表的尾结点// 如果index大于链表的长度则返回空// 如果index小于0则在头部插入节点void addAtIndex(int index, int val) {if(index size) return;//如果 index 大于链表的大小则直接返回。if(index 0) index 0;//如果 index 小于0则将其设置为0。ListNode* newNode new ListNode(val);//创建一个新节点并将其值设置为 val。ListNode* cur dummyHead;while(index) {cur cur-next;index--;}newNode-next cur-next;cur-next newNode;size;}// 删除第index个节点如果index 大于等于链表的长度直接return注意index是从0开始的void deleteAtIndex(int index) {//判断 index 是否合法如果不合法直接返回。if(index size ||index 0) {return;}//创建一个指针 cur指向虚拟头结点。ListNode* cur dummyHead;while(index) {cur cur-next;index--;}ListNode* tmp cur-next; // 创建一个临时节点指向即将删除的节点cur-next cur-next-next;// 当前节点指针指向待删除节点的下一个节点delete tmp;// 释放内存//delete命令指示释放了tmp指针原本所指的那部分内存//被delete后的指针tmp的值地址并非就是NULL而是随机值。也就是被delete后//如果不再加上一句tmpnullptr,tmp会成为乱指的野指针//如果之后的程序不小心使用了tmp会指向难以预想的内存空间tmp nullptr;size--;}void printLinkedList() {ListNode* cur dummyHead;while (cur-next ! nullptr) {cout cur-next-val ;cur cur-next;}cout endl;}private:int size;ListNode* dummyHead;
};python单链表
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextclass MyLinkedList:def __init__(self):self.dummy_head ListNode()self.size 0def get(self, index: int) - int:if index 0 or index self.size:return -1current self.dummy_head.nextfor i in range(index):current current.nextreturn current.valdef addAtHead(self, val: int) - None:self.dummy_head.next ListNode(val, self.dummy_head.next)self.size 1def addAtTail(self, val: int) - None:current self.dummy_headwhile current.next:current current.nextcurrent.next ListNode(val)self.size 1def addAtIndex(self, index: int, val: int) - None:if index 0 or index self.size:returncurrent self.dummy_headfor i in range(index):current current.nextcurrent.next ListNode(val, current.next)self.size 1def deleteAtIndex(self, index: int) - None:if index 0 or index self.size:returncurrent self.dummy_headfor i in range(index):current current.nextcurrent.next current.next.nextself.size - 1python双链表
class ListNode:def __init__(self, val0, prevNone, nextNone):self.val valself.prev prevself.next nextclass MyLinkedList:def __init__(self):self.head Noneself.tail Noneself.size 0def get(self, index: int) - int:if index 0 or index self.size:return -1if index self.size // 2:current self.headfor i in range(index):current current.nextelse:current self.tailfor i in range(self.size - index - 1):current current.prevreturn current.valdef addAtHead(self, val: int) - None:new_node ListNode(val, None, self.head)if self.head:self.head.prev new_nodeelse:self.tail new_nodeself.head new_nodeself.size 1def addAtTail(self, val: int) - None:new_node ListNode(val, self.tail, None)if self.tail:self.tail.next new_nodeelse:self.head new_nodeself.tail new_nodeself.size 1def addAtIndex(self, index: int, val: int) - None:if index 0 or index self.size:returnif index 0:self.addAtHead(val)elif index self.size:self.addAtTail(val)else:if index self.size // 2:current self.headfor i in range(index - 1):current current.nextelse:current self.tailfor i in range(self.size - index):current current.prevnew_node ListNode(val, current, current.next)current.next.prev new_nodecurrent.next new_nodeself.size 1def deleteAtIndex(self, index: int) - None:if index 0 or index self.size:returnif index 0:self.head self.head.nextif self.head:self.head.prev Noneelse:self.tail Noneelif index self.size - 1:self.tail self.tail.previf self.tail:self.tail.next Noneelse:self.head Noneelse:if index self.size // 2:current self.headfor i in range(index):current current.nextelse:current self.tailfor i in range(self.size - index - 1):current current.prevcurrent.prev.next current.nextcurrent.next.prev current.prevself.size - 1
