设计链表-虚拟节点问题,求解

Question

针对于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);
 */

Answer 1

使用虚拟头节点时，其实并不会占用链表中的任何下标。虚拟头节点只是在链表头部添加了一个额外的节点，作为链表头的前驱节点，其本身不包含有实际数据，所以不需要占用任何下标。

虚拟头节点的设置值可以根据具体情况而定。通常情况下，我们将其设置为0或-1，这样就可以方便地通过prev指针来表示当前节点的前驱节点。如果将其设置为1，则需要在遍历链表时进行一些特殊处理，才能使prev指向正确的前驱节点。

对于addAtIndex方法，由于需要找到目标位置的前驱节点，因此可以使用for循环从虚拟头节点开始遍历，直到找到目标位置的前驱节点，然后插入新节点即可。由于虚拟头节点不包含任何实际数据，所以不需要特殊处理。