自己做的网站怎么接支付宝seo推广优化服务
代码随想录-数组 | 707设计链表
- LeetCode 707-设计链表
- 解题思路
- 代码
- 复杂度
- 难点
- 总结
LeetCode 707-设计链表
题目链接
题目描述
你可以选择使用单链表或者双链表,设计并实现自己的链表。
单链表中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。
如果是双向链表,则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
解题思路
判断:
按照链表的定义书写即可。注意各函数的书写,涉及index时要先判别,
- 索引:index 是否在 [0,this.length) 之间
- 插入:index 是否在[0,this.length] 之间
代码
单链表
class MyLinkedList {public static class Node {int val;Node next;public Node(int val) {this.val = val;this.next = null;}}private Node head;private int length;public MyLinkedList() {this.length = 0;this.head = new Node(0);}public int get(int index) {if (index < 0 || index >= this.length) {return -1;}Node currentNode = this.head;for (int i=0; i<= index; i++) {currentNode = currentNode.next;}return currentNode.val;}public void addAtHead(int val) {addAtIndex(0,val);}public void addAtTail(int val) {addAtIndex(this.length,val);}public void addAtIndex(int index, int val) {if (index > this.length) {return;}Node preNode = this.head;for(int i = 0; i < index; i++) {preNode = preNode.next;}Node newNode = new Node(val);newNode.next = preNode.next;preNode.next = newNode;this.length++;}public void deleteAtIndex(int index) {if (index < 0 || index >= this.length){return;}Node preNode = this.head;for (int i = 0; i < index; i++) {preNode = preNode.next;}preNode.next = preNode.next.next;this.length--;}
}
复杂度
- 时间复杂度
涉及 index 的相关操作为 O(index), 其余为 O(1) - 空间复杂度
O(n)
难点
- 定义链表:要注意初始化链表的长度和头节点。
public MyLinkedList() {this.length = 0;this.head = new Node(0);
}
总结
还是要多熟悉熟悉。