Satrol_ 2023-04-05 10:56 采纳率: 100%
浏览 21
已结题

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

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

  • 写回答

2条回答 默认 最新

  • Dummer25 2023-04-06 16:34
    关注

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

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

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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 4月14日
  • 已采纳回答 4月6日
  • 修改了问题 4月5日
  • 创建了问题 4月5日

悬赏问题

  • ¥15 滑块验证码拖动问题悬赏
  • ¥15 Wanted but not invoked:Actually, there were zero interactions with this moc
  • ¥20 怎么驱动tb6612
  • ¥15 Arcgis 3D效果点要素
  • ¥15 在执行yolo训练脚本的时候,没有报错,在扫描val这一步后就推出执行了
  • ¥15 delphi开发的WEBSERVER改用HTTPS协议
  • ¥15 pic16f877A单片机的计数器proteus仿真失效
  • ¥100 调查 Vitis AI 中验证 .xmodel 量化后的正确性
  • ¥30 codelite全屏时file、setting那一行消失了
  • ¥15 gazebo-rviz教程