- 单链表
- 思路
- - 定义单链表的结构
- - `get(index)`
- - `addAtHead(val)`
- - `addAtTail(val)`
- - `addAtIndex(index,val)`
- - `deleteAtIndex(index)`
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:
val
和
next
。
val
是当前节点的值,
next
是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性
prev
以指示链表中的上一个节点。假设链表中的所有节点都是 0-
index
的
在链表类中实现这些功能:
get(index)
:获取链表中第index
个节点的值。如果索引无效,则返回-1
。addAtHead(val)
:在链表的第一个元素之前添加一个值为val
的节点。插入后,新节点将成为链表的第一个节点addAtTail(val)
:将值为val
的节点追加到链表的最后一个元素addAtIndex(index,val)
:在链表中的第 index 个节点之前添加值为val
的节点。如果index
等于链表的长度,则该节点将附加到链表的末尾。如果index
大于链表长度,则不会插入节点。如果index
小于0,则在头部插入节点deleteAtIndex(index)
:如果索引index
有效,则删除链表中的第index
个节点
示例:
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3
提示:
- 所有
val
值都在 [1, 1000] 之内 - *** 作次数将在 [1, 1000] 之内
- 请不要使用内置的
LinkedList
库
class Node {
int val; // 节点上存储的元素
Node next; // 指向下一个节点的指针
Node(int val) { // 节点的构造函数
this.val = val;
}
int size; // 定义结点的个数
Node head; // 定义头节点
- get(index)
- 判断
index
是否在存在的节点之内 - 通过遍历,取出节点索引的值
public int get(int index) {
// 判断index是否在存在的节点之内
if (index < 0 || index >= size || head == null) {
return -1;
}
Node temp = this.head;
// 通过遍历,取出节点索引的值
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp.val;
}
- addAtHead(val)
- 插入新节点作为新的头节点
- 节点数增加1
public void addAtHead(int val) {
Node node = new Node(val);
// 新结点指向原头结点的值
node.next = this.head;
// 新节点作为新的头节点
this.head = node;
// 节点数增加1
size++;
}
- addAtTail(val)
- 是否有节点,若无则增加的是头节点
- 找到最后一个节点,指向新结点的值
- 新结点指向
null
public void addAtTail(int val) {
// 是否有节点,若无则增加的是头节点
if (size == 0) {
this.head = new Node(val);
head.next = null;
size++;
}else {
Node temp = this.head;
while (temp.next != null) {
temp = temp.next;
}
// 找到最后一个节点,指向新结点的值
// 新结点指向`null`
Node tail = new Node(val);
tail.next = null;
temp.next = tail;
size++;
}
}
- addAtIndex(index,val)
- 当
index > size
,索引越界,不能插入节点 - 当
index < 0
,新插入的节点为头节点 - 当
index = size
,新插入的节点为最后一个节点 - 找出目标节点的前一个结点,后面的节点加1
public void addAtIndex(int index, int val) {
// 当`index > size`,索引越界,不能插入节点
if (index > this.size) {
return;
}
// 当`index < 0`,新插入的节点为头节点
if (index <= 0) {
addAtHead(val);
return;
}
// 当`index = size`,新插入的节点为最后一个节点
if (index == this.size) {
addAtTail(val);
return;
}
// 找出目标节点的前一个结点
Node temp = this.head;
for (int i = 0; i < index - 1; i++) {
temp = temp.next;
}
// 该位置插入新节点,后面的节点加1
Node insertNode = new Node(val);
insertNode.next = temp.next;
temp.next = insertNode;
size++;
}
- deleteAtIndex(index)
- 判断
index
是否在存在的节点之内 - 头节点分开讨论
- 通过遍历,取出节点索引的值并删除
- 节点数减1
public void deleteAtIndex(int index) {
// 判断`index`是否在存在的节点之内
if (index < 0 || index >= this.size) {
return;
}
// 头节点分开讨论
if (index == 0) {
if (size != 1) {
Node temp = this.head.next;
this.head =temp;
size--;
return;
}else {
this.head = null;
size--;
return;
}
}
Node temp = this.head;
// 通过遍历,取出节点索引的值并删除
for (int i = 0; i < index - 1; i++) {
temp = temp.next;
}
Node deleteNode = temp.next;
temp.next = deleteNode.next;
// 节点数减1
size--;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)