。

如果索引无效#xff0c;则返回-1。

addAtHead(val)#xff1a;在链表的第一个元素之前添加一个值为

val

的节点。

插入后#xff0c;新节点将成为链表的第一个节点。

ad…设计链表

在链表类中实现这些功能

个节点的值。

如果索引无效则返回-1。

addAtHead(val)在链表的第一个元素之前添加一个值为

val

的节点。

插入后新节点将成为链表的第一个节点。

addAtTail(val)将值为

val

的节点追加到链表的最后一个元素。

addAtIndex(index,val)在链表中的第

index

大于链表长度则不会插入节点。

如果index小于0则在头部插入节点。

deleteAtIndex(index)如果索引

index

这道题目我觉得是链表部分最好的练习链表操作的一道题目虽然不一定是考的频率最高的。

为什么这么说

删除元素新增元素查询元素

根据上一篇文章移除链表元素我们可以知道这里需要一个虚拟头结点来处理删除操作。

分析一下

get(index)、deleteAtIndex(index)、

addAtIndex(index,val)三个方法。

我们先从难的开始

正常插入

找到需要插入的前驱节点注意一定要是前驱节点也就是上图中C.new

newNodesize

preNode.next;}//这一步很重要顺序不能反。

//一定是新节点先指向下一个然后再断开前驱节点的nextnewLinedList.next

newLinedList;size;}话说回来因为我们是用size

虚拟头节点所以插入头、尾只是size的值不同所以不会有什么特殊处理的地方。

删除操作也是一样。

deleteAtIndex(index)

遍历到需要删除的节点的前驱节点黑人问号脸又是前驱节点大家可以想一下为什么不管是新增还是删除都需要前驱节点

删除很简单

dummyHead.next;}//删除节点dummyHead.next

dummyHead.next.next;size--;}get(index)

get其实和删除差不多但是唯一需要注意的是我们是虚拟头结点所以在遍历获取到的节点是前驱节点返回的是

preNode.next.val

dummyHead.next;}//注意是虚拟头结点所以需要返回next.valreturn

public

preNode.next;}//这一步很重要顺序不能反。

//一定是新节点先指向下一个然后再断开前驱节点的nextnewLinedList.next

int

dummyHead.next;}//注意是虚拟头结点所以需要返回next.valreturn

void

dummyHead.next;}//删除节点dummyHead.next

dummyHead.next.next;size--;}public

void

删除、更新操作。

注意get方法获取的返回的值应该是preNode.next.val。

新增节点的时候注意下代码顺序。