针对于leetcode设计链表问题
如果使用虚拟头节点来解决此问题
虚拟头节点占用下标吗?
如果不占用下标为什么此题初始化虚拟头节点要设置为0(我觉得应该是假设链表中的所有节点下标从 0 开始)
如果占用下标为什么,后面索引我认为都会出现问题
就比如addAtIndex,我需要在index的位置上加上一个元素,那么我肯定需要获取index前一个节点吧,我这里用了for循环,从0开始遍历到index - 1,假如我要找下标为2到节点,根据prev = prev.next后移两位,虚拟节点不占用0了嘛,后移两位不就相当于是下标索引的那个节点,但我要的是前一个节点,所以会出问题(这是我认为的)
但是下面的代码可以正常执行
或者说虚拟头节点什么时候设置0
什么时候该设置1呢
求指点
class ListNode{
int val;
ListNode next;
ListNode(){}
ListNode(int val){
this.val = val;
}
}
class MyLinkedList {
//定义链表的长度
int size = 0;
//定义虚拟头节点
ListNode head;
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
public int get(int index) {
if(index < 0 || size <= index){
return -1;
}
//遍历链表
ListNode currentNode = head;
for(int i = 0;i<=index;i++){
currentNode = currentNode.next;
}
return currentNode.val;
}
public void addAtHead(int val) {
ListNode newNode = new ListNode(val);
newNode.next = head.next;
head.next = newNode;
size++;
}
public void addAtTail(int val) {
ListNode pre = head;
ListNode newNode = new ListNode(val);
while(pre.next != null){
pre = pre.next;
}
size++;
newNode.next = pre.next;
pre.next = newNode;
}
public void addAtIndex(int index, int val) {
if(index > size){
return;
}
if(index < 0){
index = 0;
}
size++;
ListNode prev = head;
ListNode newNode = new ListNode(val);
for(int i = 0;i<index;i++){
prev = prev.next;
}
newNode.next = prev.next;
prev.next = newNode;
}
public void deleteAtIndex(int index) {
if(index >= size || index < 0){
return;
}
size--;
//如果要删除的是头节点那么直接head后移
if(index == 0){
head = head.next;
return;
}
ListNode prev = head;
for(int i = 0;i < index;i++){
prev = prev.next;
}
prev.next = prev.next.next;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/