设计链表
题目
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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
这题有点特殊，与其说是题不如说是熟悉如何实现操控链表的常见方法
参考https://www.cnblogs.com/DAYceng/p/17047323.html中的实例代码以及题题目给的模板得知
我们需要先自行定义节点类ListNode并初始化链表，这里使用的是单链表，定义如下：
class ListNode{
int val;
ListNode next;
//定义三个构造器
public ListNode(){
}
public ListNode(int val){
this.val = val;
}
public ListNode(int val, ListNode next){
this.val = val;
this.next = next;
}
}
class MyLinkedList {
int size;//链表节点个数
ListNode dummy;//定义虚拟头节点
//用于初始化一个链表
public MyLinkedList() {
//初始化链表的size和虚拟头节点
size = 0;
dummy = new ListNode(0);
}
public int get(int index) {
}
public void addAtHead(int val) {
}
public void addAtTail(int val) {
}
public void addAtIndex(int index, int val) {
}
public void deleteAtIndex(int index) {
}
}
题目需要实现五个函数，下面逐一介绍
首先需要明确几点：
1、题目中，index是从0开始的，也就是说头节点的值也应该能够获取
2、统一使用虚拟节点，方便进行CRUD
获取第n个节点的值
思路
获取链表的值不能带入其他数据结构的思维
获取链表的值的方式就是遍历链表（这也是链表相对于数组的一大缺陷，慢）
要哪个节点就要从头节点遍历到那个才行
基于此，我们便可以开始设计这个方法了
不过还有几个点需要注意：
- 需要考虑n的范围（小于0不行，大于链表size-1也不行）
- 不能直接操作头节点，要不然找不回来原有的链表了
代码实现
class ListNode{
int val;
ListNode next;
//定义三个构造器
public ListNode(){
}
public ListNode(int val){
this.val = val;
}
public ListNode(int val, ListNode next){
this.val = val;
this.next = next;
}
}
class MyLinkedList {
int size;//链表节点个数
ListNode dummy;//定义虚拟头节点
//用于初始化一个链表
public MyLinkedList() {
//初始化链表的size和虚拟头节点
size = 0;
dummy = new ListNode(0);
}
public int get(int index) {
//排除非法范围的n
if(index < 0 || index > size - 1){
return -1;
}
//定义当前节点cur
ListNode cur = dummy;
//遍历链表直到找到第index个节点
for(int i = 0; i <= index; i++){
cur = cur.next;
}
return cur.val; //返回该节点的值
}
...
}
ps：
在C++中可以用"while+运算式"来遍历，如下：
while(index){
cur = cur.next;
index--;
}
在Java中好像不能这么写，Java中的while需要的是一个条件式
头部插入节点
（按解题的思路顺序，应该先解决“第n个节点前插入节点”）
思路
如果搞清楚怎么在第n个节点前插入节点，这里的做法其实是一样的
代码实现
public void addAtHead(int val) {
//写法1：直接调用addAtIndex
//addAtIndex(0, val);
//写法2：
ListNode pre = dummy;//虚拟节点
ListNode cur = dummy.next;//这个才是真正的“头节点”所在的位置
//新建一个节点
ListNode node4add = new ListNode(val);
node4add.next = pre.next;
pre.next = node4add;
size++;
}
尾部插入节点
（按解题的思路顺序，应该先解决“第n个节点前插入节点”）
思路
同理
代码实现
public void addAtTail(int val) {
//写法1：直接调用addAtIndex
//addAtIndex(index, val);
//写法2：直接遍历链表，然后在末尾加
// ListNode pre = dummy;//虚拟节点
// ListNode cur = dummy.next;//这个才是真正的“头节点”所在的位置
ListNode cur = dummy;
while(cur.next != null){//遍历结束条件是遇到next为空的节点
cur = cur.next;
}
ListNode node4add = new ListNode(val);
cur.next = node4add;
size++;
}
ps：寻找末尾节点的遍历结束条件是遍历到.next为null的节点
第n个节点前插入节点
//在指定位置前插入新的节点
//要求
// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果 index 大于链表的长度，则返回空
思路
0、判定index是否合法
1、先找到第n个节点
2、然后将新创建的节点的next指向pre节点（指向dummy）的next（如果是只定义cur，cur指向dummy，那就是指向cur.next）
或者
代码实现
class ListNode{
int val;
ListNode next;
//定义三个构造器
public ListNode(){
}
public ListNode(int val){
this.val = val;
}
public ListNode(int val, ListNode next){
this.val = val;
this.next = next;
}
}
class MyLinkedList {
int size;//链表节点个数
ListNode dummy;//定义虚拟头节点
//用于初始化一个链表
public MyLinkedList() {
//初始化链表的size和虚拟头节点
size = 0;
dummy = new ListNode(0);
}
...
//在指定位置前插入新的节点
//要求
// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果 index 大于链表的长度，则返回空
public void addAtIndex(int index, int val) {
//先判定index是否合法
if(index > size){
return;
}else if(index < 0){
index = 0;
}
//有两种写法：使用临时节点变量pre指代dummyhead+cur指代当前节点、直接使用一个cur
// //写法1：
// ListNode pre = dummy;
// ListNode cur = dummy.next;
// //遍历寻找待修改的节点
// for(int i = 0; i < index; i++){
// pre = cur;
// cur = cur.next;
// }
// //找到了就开始插
// //新建用来插入的节点
// ListNode node4add = new ListNode(val);
// //按步骤插入
// node4add.next = pre.next;
// pre.next = node4add;
// size++;
// //写法2：
ListNode cur = dummy;
//遍历找点
for(int i = 0; i < index; i++){
cur = cur.next;
}
//新建用来插入的节点
ListNode node4add = new ListNode(val);
node4add.next = cur.next;
cur.next = node4add;
size ++;
}
...
}
ps：别忘了size ++;
删除第n个节点
思路
cur指向A节点（dummy节点），记住，当前节点应该是cur的下一个节点，即B节点（cur.next）
删除当前第n个节点就是删除cur.next
那么只需要把cur的下一个节点的地址指向B的下一个节点，即C节点（cur.next.next）
代码实现
public void deleteAtIndex(int index) {
if(index < 0 || index >= size){
return;
}
size--;
//还是先找到要删除的节点
// ListNode pre = dummy;
// ListNode cur = dummy.next;
ListNode cur = dummy;
// while(index){
// cur = cur.next;
// }
for(int i = 0; i < index; i++){
cur = cur.next;
}
//找到后开始删除
// pre.next = cur.next;
// cur.next = null;
cur.next = cur.next.next;
}
完整代码
class ListNode{
int val;
ListNode next;
//定义三个构造器
public ListNode(){
}
public ListNode(int val){
this.val = val;
}
public ListNode(int val, ListNode next){
this.val = val;
this.next = next;
}
}
class MyLinkedList {
int size;//链表节点个数
ListNode dummy;//定义虚拟头节点
//用于初始化一个链表
public MyLinkedList() {
//初始化链表的size和虚拟头节点
size = 0;
dummy = new ListNode(0);
}
public int get(int index) {
if(index < 0 || index > size - 1){
return -1;
}
//定义当前节点cur
ListNode cur = dummy;
// while(index){
// cur = cur.next;
// index--;
// }
for(int i = 0; i <= index; i++){
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
//写法1：直接调用addAtIndex
//addAtIndex(0, val);
//写法2：
ListNode pre = dummy;//虚拟节点
ListNode cur = dummy.next;//这个才是真正的“头节点”所在的位置
//新建一个节点
ListNode node4add = new ListNode(val);
node4add.next = pre.next;
pre.next = node4add;
size++;
}
public void addAtTail(int val) {
//写法1：直接调用addAtIndex
//addAtIndex(index, val);
//写法2：直接遍历链表，然后在末尾加
// ListNode pre = dummy;//虚拟节点
// ListNode cur = dummy.next;//这个才是真正的“头节点”所在的位置
ListNode cur = dummy;
while(cur.next != null){//遍历结束条件是遇到next为空的节点
cur = cur.next;
}
ListNode node4add = new ListNode(val);
cur.next = node4add;
size++;
}
//在指定位置前插入新的节点
//要求
// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果 index 大于链表的长度，则返回空
public void addAtIndex(int index, int val) {
//先判定index是否合法
if(index > size){
return;
}else if(index < 0){
index = 0;
}
//有两种写法：使用临时节点变量pre指代dummyhead+cur指代当前节点、直接使用一个cur
// //写法1：
// ListNode pre = dummy;
// ListNode cur = dummy.next;
// //遍历寻找待修改的节点
// // while(index){
// // cur = cur.next;
// // index--;
// // }
// for(int i = 0; i < index; i++){
// pre = cur;
// cur = cur.next;
// }
// //找到了就开始插
// //新建用来插入的节点
// ListNode node4add = new ListNode(val);
// //按步骤插入
// node4add.next = pre.next;
// pre.next = node4add;
// size++;
// //写法2：
ListNode cur = dummy;
//遍历找点
// while(index){
// cur.next = cur.next.next;//cur = cur.next也行，就多遍历一个dummy节点的区别
// index --;
// }
for(int i = 0; i < index; i++){
cur = cur.next;
}
//新建用来插入的节点
ListNode node4add = new ListNode(val);
node4add.next = cur.next;
cur.next = node4add;
size ++;
}
public void deleteAtIndex(int index) {
if(index < 0 || index >= size){
return;
}
size--;
//还是先找到要删除的节点
// ListNode pre = dummy;
// ListNode cur = dummy.next;
ListNode cur = dummy;
// while(index){
// cur = cur.next;
// }
for(int i = 0; i < index; i++){
cur = cur.next;
}
//找到后开始删除
// pre.next = cur.next;
// cur.next = null;
cur.next = cur.next.next;
}
}