版本说明
当前版本号[20230818]。
版本 | 修改说明 |
---|---|
20230818 | 初版 |
目录
文章目录
- 版本说明
- 目录
- 707.设计链表
- 思路
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点
- 单链表角度
- 总结
707.设计链表
力扣题目链接
更多内容可点击此处跳转到代码随想录,看原版文件
题意:
在链表类中实现这些功能:
- get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
- addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
- addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
- deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。
思路
如果对链表的基础知识还不太懂和对链表的虚拟头结点不清楚,,可以看这篇文章:关于链表,你该了解这些!
删除链表节点:
添加链表节点:
这道题目设计链表的五个接口:
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点
可以说这五个接口,已经覆盖了链表的常见操作,是练习链表操作非常好的一道题目
我们也将从这五个接口中,讲解每一个接口的思路让大家对本题有更加清晰的认知。
获取链表第index个节点的数值
-
检查index是否有效,如果index小于0或大于等于链表长度,则返回-1。
-
从头结点开始,定义一个指针currentNode指向head节点(虚拟头结点的下一个节点)。
【为什么要定义指针currentNode呢? 答:因为我们操作完链表后,要返回头结点,如果直接操作头结点,那么返回头结点的时候头结点的值已经改了。】
-
通过循环遍历,将currentNode指针移动index次,直到达到目标位置。
-
循环过程中,每次将currentNode指针指向currentNode的下一个节点,即currentNode = currentNode.next。
-
循环结束后,currentNode指针指向第index个节点。
-
返回currentNode的值,即currentNode.val,作为结果。
在链表的最前面插入一个节点
-
创建一个新的节点,将值设置为val。
-
将新节点的next指针指向当前的头节点,即新节点的next指向原来的第一个节点。
注:此时我们新建了一个新的结点new node ,然后形成下图的趋势去插入结点
那在指示下,我们就会发现head所代表的下一个区域无法表达出来,因为:原先的head区域我们是可以用 dymghead - > next 来表示了,但又因为我们已经用其表示new node 了,已经修改了 dymghead - > next 的值去了,就无法再表达 head 的区域了。
从上面的教训我们就知道,应该先表达new node 和 head 的关系,再表达 dymghead , 才不会出现修改了值,无法表达的情况。
于是先 表达 new node - > next = dymghead - > next , 再表达dymghead - > next= new node ,即可。
3.将链表的头节点指向新节点,使新节点成为新的头节点。
在链表的最后面插入一个节点
- 创建一个新的节点,将值设置为val。
- 如果链表为空,即**链表的头节点为null,将链表的头节点指向新节点。**新节点成为链表的唯一节点。
- 如果链表不为空,找到链表的最后一个节点。从头节点开始遍历链表,通过next指针逐个访问节点,直到找到最后一个节点。
- 将最后一个节点的next指针指向新节点,将新节点插入到链表的最后一个位置。
在链表第index个节点前面插入一个节点
- 创建一个新的节点,将值设置为val。
- 检查index的值是否为0,如果是0,则直接调用addAtHead(val)方法,在链表的头部插入节点。
- 如果index大于0,需要找到链表的第index-1个节点。
- 从头节点开始遍历链表,通过next指针逐个访问节点,直到找到第index-1个节点。
- 将新节点的next指针指向第index个节点。
- 将第index-1个节点的next指针指向新节点。
删除链表的第index个节点
- 检查index是否有效,如果index小于0或大于等于链表长度,则直接返回,不进行删除操作。
- 如果index有效,分为两种情况处理删除操作:
- 如果index为0,即要删除的是链表的第一个节点。将链表的头节点指向第二个节点,即头节点的next指针所指向的节点。
- 如果index不为0,需要找到第index-1个节点。从头节点开始遍历链表,通过next指针逐个访问节点,直到找到第index-1个节点。
- 将第index-1个节点的next指针指向第index+1个节点,即跳过要删除的节点。
链表操作的两种方式:
- 直接使用原来的链表来进行操作。
- 设置一个虚拟头结点在进行操作。
下面采用的设置一个虚拟头结点(这样更方便一些,大家看代码就会感受出来)。
单链表角度
这段代码实现了一个单链表数据结构,包括了链表的初始化、插入、删除和获取等操作。让我们逐步分析每个方法的作用:
-
ListNode类:用来表示链表的节点,包含一个整数val表示节点的值,以及一个指向下一个节点的指针next。
//单链表 class ListNode { // 定义链表节点类 int val; // 节点值 ListNode next; // 指向下一个节点的指针 ListNode() { } // 默认构造函数 ListNode(int val) { // 带参构造函数 this.val = val; } }
-
MyLinkedList类:实际上就是单链表的实现,包含以下几个核心属性和方法:
-
size:保存链表中节点的个数。
-
head:虚拟头结点,作为链表的起始位置。
-
MyLinkedList():构造函数,用来初始化链表。将size设置为0,并创建一个值为0的虚拟头结点。
int size; // 链表元素个数 //虚拟头结点 ListNode head; // 虚拟头节点 //初始化链表 public MyLinkedList() { // 构造函数 size = 0; // 初始化链表大小为0 head = new ListNode(0); // 创建一个值为0的虚拟头节点 }
-
get(int index):**获取第index个节点的值。**如果index越界,返回-1。从头结点开始遍历链表,找到第index+1个节点,并返回其值。
//获取第index个节点的数值,注意index是从0开始的,第0个节点就是头结点 public int get(int index) { // 获取链表中第index个节点的值 //如果index非法,返回-1 if (index < 0 || index >= size) { // 如果index小于0或大于等于链表大小,则索引非法,返回-1 return -1; } ListNode currentNode = head; // 从头结点开始遍历链表 //包含一个虚拟头节点,所以查找第 index+1 个节点 for (int i = 0; i <= index; i++) { // 遍历找到第index+1个节点(包括虚拟头节点) currentNode = currentNode.next; } return currentNode.val; // 返回第index个节点的值 }
- addAtHead(int val):在链表的最前面插入一个节点,等价于在第0个元素前添加。调用addAtIndex(0, val)方法实现。
- addAtTail(int val):在链表的最后插入一个节点,等价于在末尾元素后添加。调用addAtIndex(size, val)方法实现。
//在链表最前面插入一个节点,等价于在第0个元素前添加 public void addAtHead(int val) { // 在链表最前面插入一个节点 addAtIndex(0, val); // 调用addAtIndex方法,在第0个位置插入节点 } //在链表的最后插入一个节点,等价于在(末尾+1)个元素前添加 public void addAtTail(int val) { // 在链表最后插入一个节点 addAtIndex(size, val); // 调用addAtIndex方法,在末尾位置插入节点 }
- addAtIndex(int index, int val):在第index个节点之前插入一个新节点,如果index等于链表的长度,则插入为尾结点;如果index大于链表的长度,不进行插入。首先进行边界判断,然后找到第index个节点的前驱节点,创建一个新的节点并将其插入到合适的位置。
// 在第 index 个节点之前插入一个新节点,例如index为0,那么新插入的节点为链表的新头节点。 // 如果 index 等于链表的长度,则说明是新插入的节点为链表的尾结点 // 如果 index 大于链表的长度,则返回空 public void addAtIndex(int index, int val) { // 在第index个节点之前插入一个新节点 if (index > size) { // 如果index大于链表大小,不进行插入,直接返回 return; } if (index < 0) { // 如果index小于0,将index调整为0 index = 0; } size++; // 链表大小加1 //找到要插入节点的前驱 ListNode pred = head; // 找到要插入节点的前驱节点,从头结点开始遍历链表 for (int i = 0; i < index; i++) { // 遍历找到第index个节点的前驱节点 pred = pred.next; } ListNode toAdd = new ListNode(val); // 创建一个新的节点 toAdd.next = pred.next; // 将新节点的next指针指向前驱节点的next指针指向的节点 pred.next = toAdd; // 将前驱节点的next指针指向新节点,实现节点插入 }
- deleteAtIndex(int index):删除第index个节点。如果index越界,不进行删除。首先进行边界判断,然后找到第index个节点的前驱节点,将其next指针指向下一个节点的next指针,实现节点的删除。
-
//删除第index个节点
public void deleteAtIndex(int index) { // 删除第index个节点
if (index < 0 || index >= size) { // 如果index小于0或大于等于链表大小,不进行删除,直接返回
return;
}
size--; // 链表大小减1
if (index == 0) { // 如果要删除的是头结点
head = head.next; // 将头结点指向下一个节点即可完成删除操作
return;
}
ListNode pred = head; // 找到要删除节点的前驱节点,从头结点开始遍历链表
for (int i = 0; i < index; i++) { // 遍历找到第index个节点的前驱节点
pred = pred.next;
}
pred.next = pred.next.next; // 将前驱节点的next指针指向要删除节点的下一个节点,实现节点的删除
}
这段代码实现了基本的单链表操作,并提供了对链表进行插入、删除和获取操作的接口。可以用来构建和操作一个链表数据结构。
单链表示例代码:
//单链表
class ListNode { // 定义链表节点类
int val; // 节点值
ListNode next; // 指向下一个节点的指针
ListNode() {
} // 默认构造函数
ListNode(int val) { // 带参构造函数
this.val = val;
}
}
class MyLinkedList { // 定义链表类
//size存储链表元素的个数
int size; // 链表元素个数
//虚拟头结点
ListNode head; // 虚拟头节点
//初始化链表
public MyLinkedList() { // 构造函数
size = 0; // 初始化链表大小为0
head = new ListNode(0); // 创建一个值为0的虚拟头节点
}
//获取第index个节点的数值,注意index是从0开始的,第0个节点就是头结点
public int get(int index) { // 获取链表中第index个节点的值
//如果index非法,返回-1
if (index < 0 || index >= size) { // 如果index小于0或大于等于链表大小,则索引非法,返回-1
return -1;
}
ListNode currentNode = head; // 从头结点开始遍历链表
//包含一个虚拟头节点,所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) { // 遍历找到第index+1个节点(包括虚拟头节点)
currentNode = currentNode.next;
}
return currentNode.val; // 返回第index个节点的值
}
//在链表最前面插入一个节点,等价于在第0个元素前添加
public void addAtHead(int val) { // 在链表最前面插入一个节点
addAtIndex(0, val); // 调用addAtIndex方法,在第0个位置插入节点
}
//在链表的最后插入一个节点,等价于在(末尾+1)个元素前添加
public void addAtTail(int val) { // 在链表最后插入一个节点
addAtIndex(size, val); // 调用addAtIndex方法,在末尾位置插入节点
}
// 在第 index 个节点之前插入一个新节点,例如index为0,那么新插入的节点为链表的新头节点。
// 如果 index 等于链表的长度,则说明是新插入的节点为链表的尾结点
// 如果 index 大于链表的长度,则返回空
public void addAtIndex(int index, int val) { // 在第index个节点之前插入一个新节点
if (index > size) { // 如果index大于链表大小,不进行插入,直接返回
return;
}
if (index < 0) { // 如果index小于0,将index调整为0
index = 0;
}
size++; // 链表大小加1
//找到要插入节点的前驱
ListNode pred = head; // 找到要插入节点的前驱节点,从头结点开始遍历链表
for (int i = 0; i < index; i++) { // 遍历找到第index个节点的前驱节点
pred = pred.next;
}
ListNode toAdd = new ListNode(val); // 创建一个新的节点
toAdd.next = pred.next; // 将新节点的next指针指向前驱节点的next指针指向的节点
pred.next = toAdd; // 将前驱节点的next指针指向新节点,实现节点插入
}
//删除第index个节点
public void deleteAtIndex(int index) { // 删除第index个节点
if (index < 0 || index >= size) { // 如果index小于0或大于等于链表大小,不进行删除,直接返回
return;
}
size--; // 链表大小减1
if (index == 0) { // 如果要删除的是头结点
head = head.next; // 将头结点指向下一个节点即可完成删除操作
return;
}
ListNode pred = head; // 找到要删除节点的前驱节点,从头结点开始遍历链表
for (int i = 0; i < index; i++) { // 遍历找到第index个节点的前驱节点
pred = pred.next;
}
pred.next = pred.next.next; // 将前驱节点的next指针指向要删除节点的下一个节点,实现节点的删除
}
总结
针对这个题目,可以使用一个单链表的数据结构来实现所需的功能。
首先,需要定义一个链表节点的类,节点包含一个值和一个指向下一个节点的指针。
接下来,可以在链表类中实现以下功能:
get(index)
:从头节点开始遍历链表,直到找到第index
个节点,然后返回该节点的值。如果遍历过程中超出了链表的长度,则返回 -1。addAtHead(val)
:创建一个新的节点,将新节点的指针指向原来的头节点,然后将头指针指向新节点。addAtTail(val)
:从头节点开始遍历链表,直到找到最后一个节点,将新节点追加到最后一个节点的指针上。addAtIndex(index, val)
:如果index
小于等于 0,则调用addAtHead(val)
方法;如果index
等于链表的长度,则调用addAtTail(val)
方法;如果index
大于链表长度,则不进行任何操作;否则,从头节点开始遍历链表,找到第index - 1
个节点,然后创建一个新节点,将新节点的指针指向原来第index
个节点的指针,再将第index - 1
个节点的指针指向新节点。deleteAtIndex(index)
:如果index
小于 0 或者大于等于链表的长度,则不进行任何操作;如果index
等于 0,则将头指针指向第二个节点;否则,从头节点开始遍历链表,找到第index - 1
个节点,将其指针指向第index + 1
个节点。
以上就是分析解题思路的主要步骤。实际编写代码时,需要根据具体语言的特点进行实现,并考虑一些边界条件的处理。
单链表与双链表示例代码:
//双链表
class ListNode{
int val;
ListNode next,prev;
ListNode() {};
ListNode(int val){
this.val = val;
}
}
class MyLinkedList {
//记录链表中元素的数量
int size;
//记录链表的虚拟头结点和尾结点
ListNode head,tail;
public MyLinkedList() {
//初始化操作
this.size = 0;
this.head = new ListNode(0);
this.tail = new ListNode(0);
//这一步非常关键,否则在加入头结点的操作中会出现null.next的错误!!!
head.next=tail;
tail.prev=head;
}
public int get(int index) {
//判断index是否有效
if(index<0 || index>=size){
return -1;
}
ListNode cur = this.head;
//判断是哪一边遍历时间更短
if(index >= size / 2){
//tail开始
cur = tail;
for(int i=0; i< size-index; i++){
cur = cur.prev;
}
}else{
for(int i=0; i<= index; i++){
cur = cur.next;
}
}
return cur.val;
}
public void addAtHead(int val) {
//等价于在第0个元素前添加
addAtIndex(0,val);
}
public void addAtTail(int val) {
//等价于在最后一个元素(null)前添加
addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {
//index大于链表长度
if(index>size){
return;
}
//index小于0
if(index<0){
index = 0;
}
size++;
//找到前驱
ListNode pre = this.head;
for(int i=0; i<index; i++){
pre = pre.next;
}
//新建结点
ListNode newNode = new ListNode(val);
newNode.next = pre.next;
pre.next.prev = newNode;
newNode.prev = pre;
pre.next = newNode;
}
public void deleteAtIndex(int index) {
//判断索引是否有效
if(index<0 || index>=size){
return;
}
//删除操作
size--;
ListNode pre = this.head;
for(int i=0; i<index; i++){
pre = pre.next;
}
pre.next.next.prev = pre;
pre.next = pre.next.next;
}
}
new ListNode(val);
newNode.next = pre.next;
pre.next.prev = newNode;
newNode.prev = pre;
pre.next = newNode;
}
public void deleteAtIndex(int index) {
//判断索引是否有效
if(index<0 || index>=size){
return;
}
//删除操作
size--;
ListNode pre = this.head;
for(int i=0; i<index; i++){
pre = pre.next;
}
pre.next.next.prev = pre;
pre.next = pre.next.next;
}
}