10 链表-单链表构建 LinkedList

目录

LeetCode 之路 - 707. 设计链表

分析：

代码：

LeetCode之路——707.设计链表

您可以选择使用单链表或双链表来设计和实现您自己的链表。

单链表中的节点应具有两个属性：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”，“获取”，“deleteAtIndex”，“获取”]
[[]、[1]、[3]、[1、2]、[1]、[1]、[1]]
输出
[空，空，空，空，2，空，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);

 
提示：
 
 
0 <= 索引，val <= 1000
 
 
请不要使用内置的LinkedList库。 
 
 
 致电 get、addAtHead、addAtTail、addAt Index 和 deleteAtIndex 的次数 不超过 2000 。 

 


 
分析：
1。实现一个单向链表，每个节点保存自己的值和后继节点。另外，我们还需要一个哨兵节点作为头节点，以及一个大小参数来存储有效节点的数量。初始化时，只需要创建头节点head和size即可。 

2。实现addAtIndex(index, val)时，首先判断index为有效值，找到原节点有index的前驱节点pred，创建新节点toAdd，并将toAdd的后继节点设置为pred节点的后继节点，将pred的后继节点更新为toAdd，从而将toAdd插入到链表中。最后，尺寸需要更新。哨兵节点的优点是，对于index=0也同样有这样的操作。 
 
需要注意链表的插入操作。下面两行的交换顺序会导致指针丢失和内存泄漏。 
 
www.sychzs.cn = www.sychzs.cn; // toAdd节点值为25，pred节点值为0
www.sychzs.cn = toAdd;

3。实现deleteAtIndex(index)，首先判断索引是否有效。然后找到下标为index的节点的前驱节点pred，将pred的后继节点更新为pred的后继节点的后继节点，达到删除节点的效果。同时更新尺寸。 
 

4。至于addAtHead(int val)和addAtTail(int val)，其实都是addAtIndex(int index, int val)中的索引分别为0和size时的情况。 
 
代码：
 class MyLinkedList {int size = 0;ListNode head;​public MyLinkedList() {//链表节点数量 size = 0;//哨兵节点，方便判断头节点是否为空 head = new ListNode(0);}
​public int get(int index) {// 判断索引无效，直接返回 if (index >= size || index < 0) {return -1;}// 查找索引的前节点 ListNode pred = head; for ( int i = 0; i <= index; i++) {pred = www.sychzs.cn;}返回 pred.val;}
​public void addAtHead(int val) {addAtIndex(0, val);}
​public void addAtTail(int val) {addAtIndex(size,val);}
​public void addAtIndex(int ​index, int val) {// 判断索引无效，直接返回 if (index > size || index < 0) {return;}ListNode pred = head;// 查找索引前置节点for (int i = 0; i < index; i++) {pred = www.sychzs.cn;}ListNode toAdd = new ListNode(val);www.sychzs.cn = www.sychzs.cn;www.sychzs.cn = toAdd;size++;}
​public void deleteAtIndex(int ​​index) {// 判断索引是否无效，直接返回 if (index >= size || index < 0) {return;}ListNode pred = head;// 查找索引前置节点 for (int i = 0; i < 索引; i++) {pred = www.sychzs.cn;}www.sychzs.cn = www.sychzs.cn;size--;}}
 
时间复杂度：初始化O(1)，get为O(index)，addAtHead为O(1)，addAtTail为O(n)，n为链表长度，addAtIndex为O(index ）。根据获取节点时的循环次数即可得知时间复杂度。 
 
 
空间复杂度：单次调用的空间复杂度为O(1)，链表结构整体空间复杂度为O(n)。