免费织梦bbs网站模板秦洁婷seo博客

设计链表

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

思路

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

1. 删除元素
2. 新增元素
3. 查询元素

上述对链表的操作都已经涉及。

类中的属性

根据题目第4点要求，我们可以知道，这个自定义链表中一定有个 size 属性，记录当前链表的长度。（不然你怎么判断index?）
根据上一篇文章移除链表元素我们可以知道，这里需要一个虚拟头结点来处理删除操作。

各个方法的代码

分析一下 addAtHead() 和 addAtTail()可以合并到 addAtIndex()方法中
大概就是：
addAtHead(val) == addAtIndex(0,val)
addAtTail(val) == addAtIndex(size,val)
所以，我们真正需要写的方法只有 get(index)、deleteAtIndex(index)、 addAtIndex(index,val)三个方法。我们先从难的开始

addAtIndex(index,val)

先不考虑头尾这两个特例。

正常插入

我们先想一下在正常结点中插入数据

1. 找到需要插入的前驱节点（注意一定要是前驱节点）也就是上图中C.
2. new 一个新节点
3. newNode的next -> 前驱节点的next
4. 前驱节点的next -> newNode
5. size++

插入头（head）

我们这里使用的虚拟节点，采用上述方法可以直接插入

插入尾(tail)

仔细一想，好像也可以，没问题。
相关代码：

 public void addAtIndex(int index,int val) {if (index > size) {return;} else if (index <= 0) {index = 0;}ListNode newLinedList = new ListNode(val);ListNode preNode = head;for (int i = 0; i < index; i++) {preNode = preNode.next;}//这一步很重要，顺序不能反。//一定是新节点先指向下一个，然后再断开前驱节点的nextnewLinedList.next = preNode.next;preNode.next = newLinedList;size++;}

话说回来，因为我们是用size+ 虚拟头节点，所以插入头、尾只是size的值不同，所以不会有什么特殊处理的地方。删除操作也是一样。

deleteAtIndex(index)

遍历到需要删除的节点的前驱节点（黑人问号脸？又是前驱节点？大家可以想一下，为什么不管是新增还是删除都需要前驱节点）
删除很简单 ：伪代码： preNode.next = preNode.next.next
实际代码：

 public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}ListNode dummyHead = head;for (int i = 0; i < index; i++) {dummyHead = dummyHead.next;}//删除节点dummyHead.next = dummyHead.next.next;size--;}

get(index)

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

    public int get(int index) {//这里需要带等号if (index < 0 || index >= size) {return -1;}ListNode dummyHead = head;for (int i = 0; i < index; i++) {dummyHead = dummyHead.next;}//注意是虚拟头结点，所以需要返回next.valreturn dummyHead.next.val;}

代码

public class MyLinkedList {/*** 虚拟头结点*/ListNode head;int size;MyLinkedList() {size = 0;head = new ListNode(0);}public void addAtIndex(int index, int val) {if (index > size) {return;} else if (index <= 0) {index = 0;}ListNode newLinedList = new ListNode(val);ListNode preNode = head;for (int i = 0; i < index; i++) {preNode = preNode.next;}//这一步很重要，顺序不能反。//一定是新节点先指向下一个，然后再断开前驱节点的nextnewLinedList.next = preNode.next;preNode.next = newLinedList;size++;}public int get(int index) {//这里需要带等号if (index < 0 || index >= size) {return -1;}ListNode dummyHead = head;for (int i = 0; i < index; i++) {dummyHead = dummyHead.next;}//注意是虚拟头结点，所以需要返回next.valreturn dummyHead.next.val;}public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}ListNode dummyHead = head;for (int i = 0; i < index; i++) {dummyHead = dummyHead.next;}//删除节点dummyHead.next = dummyHead.next.next;size--;}public void addAtHead(int val) {addAtIndex(0, val);}public void addAtTail(int val) {addAtIndex(size, val);}}

总结

1. 利用虚拟节点处理 删除、更新操作。
2. 注意get方法获取的返回的值应该是：preNode.next.val。
3. 新增节点的时候，注意下代码顺序。