| 2024-04-07 |

# 设计链表

前言：4 号提交了 5 次全部失败这里贴一下失败的尝试，设计链表非常考研程序整体的结构一个方法出现纰漏，后面会出现各种问题。

# 题目

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性： val 和 next 。 val 是当前节点的值， next 是指向下一个节点的指针 / 引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。

int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。

void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。

void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。

void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。

void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3
提示：

0 <= index, val <= 1000

请不要使用内置的 LinkedList 库。

调用 get 、 addAtHead 、 addAtTail 、 addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

# 失败代码

public class MyLinkedNode
    {
        public int val;
        public MyLinkedNode next;
    }

    public class MyLinkedList
    {
        //虚假头节点
        public MyLinkedNode StartHead;

        public MyLinkedList()
        {
            StartHead = new MyLinkedNode();
        }

        public int Get(int index)
        {
            if (index < 0)
            {
                return -1;
            }

            //从头结点开始遍历
            MyLinkedNode curNode = StartHead.next;
            int count = 0;
            while (curNode != null && count < index)
            {
                curNode = curNode.next;
                count++;
            }

            if (curNode == null)
            {
                return -1; // 当索引超出链表长度时，返回 -1
            }

            return curNode.val;
        }

        public void AddAtHead(int val)
        {
            MyLinkedNode addNode = new MyLinkedNode();
            addNode.val = val;
            if (StartHead.next == null)  //我这里好像就弄反顺序了
            {
                StartHead.next = addNode;
            }
            else
            {
                addNode.next = StartHead.next.next;
                StartHead.next = addNode;
            }
        }

        public void AddAtTail(int val)
        {
            //遍历找到尾部节点 从头节点开始
            if (StartHead.next == null)
            {
                //链表为空
                StartHead.next = new MyLinkedNode();
                StartHead.next.val = val;
                return;
            }

            MyLinkedNode endNode = StartHead.next;

            while (endNode.next != null)
            {
                endNode = endNode.next;
            }

            endNode.next = new MyLinkedNode();
            endNode.next.val = val;
        }

        public void AddAtIndex(int index, int val)
        {
            if (index < 0)
            {
                return;
            }

            MyLinkedNode addNode = new MyLinkedNode();
            addNode.val = val;

            MyLinkedNode curNode = StartHead;
            for (int i = 0; i < index; i++)
            {
                if (curNode.next == null)
                {
                    // 当索引超出链表长度时，将节点添加到链表末尾
                    curNode.next = addNode;
                    return;
                }

                curNode = curNode.next;
            }

            // 此时 curNode 指向插入位置的前一个节点
            addNode.next = curNode.next;
            curNode.next = addNode;


            // MyLinkedNode addNode = new MyLinkedNode();
            // addNode.val = val;
            // MyLinkedNode curNode = StartHead.next;
            // if(curNode == null){
            //     //如果头结点为空 链表为空
            //     StartHead.next = addNode;
            //     return;
            // }
            // //头结点不为空

            // //前一个节点
            // MyLinkedNode lastNode = StartHead;
            // while(index > 0){
            //     if(curNode != null && lastNode != null){
            //         lastNode = curNode;
            //         curNode = curNode.next;
            //     }else if(curNode == null && index == 0){
            //         //等于长度了
            //         lastNode.next = addNode;
            //         return;
            //     }else{
            //         return;
            //     }
            //     index--;
            // }
            // //插入节点在这个节点之前
            // addNode.next = curNode;
            // lastNode.next = addNode;
        }

        public void DeleteAtIndex(int index)
        {
            if (index < 0)
            {
                return;
            }

            MyLinkedNode curNode = StartHead;
            for (int i = 0; i < index; i++)
            {
                if (curNode.next == null)
                {
                    // 如果索引超出链表长度，直接返回
                    return;
                }

                curNode = curNode.next;
            }

            // 此时 curNode 指向要删除节点的前一个节点
            if (curNode.next != null)
            {
                curNode.next = curNode.next.next;
            }


            // MyLinkedNode curNode = StartHead.next;
            // MyLinkedNode beforeNode = StartHead.next;
            // if(curNode == null){
            //     return;
            // }


            // while(index > 0){
            //     if(curNode != null){
            //         beforeNode = curNode;
            //         curNode = curNode.next;
            //     }
            //     else{
            //         return;
            //     }
            //     index--;
            // }
            // //删除这个节点 之前的节点断开
            // beforeNode.next = curNode.next;
            // curNode = null;
        }
    }

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

好那写之前我决定看视频先学习一下

获取第 n 个节点的值
1. 合法性判断： n<0 且 n> size-1 都是不合法的
2. 定义临时指针 cur 为 dummyHead -> next；
3. 记住极端情况获取第 0 个的情况
头部插入节点
1. new 一个新 Node
2. new.next = dummy .next (注意这里的顺序如果和 3 反了会导致连接错误)
3. dummy.next = new
4. size++
尾部插入节点
1. cur = dummy
2. while (cur.next != null) 为空为终止条件
3. cur.next = newNode
第 n 个节点前插入节点
1. cur = dummy
2. while (n–){ cur = cur.next} n 为 0 的时候终止
3. 和插入一样如下图顺序
4. image-20240407212448058
删除第 n 个节点
1. cur= dummy
2. 第 n 个节点一定要是 cur.next 然后我们操作第 cur 个节点
3. 一样 while (n–) cur= cur.next 第 n 个为 cur.next
4. cur.next = cur.next.next; 指向下下个为 null 也不要紧 n 记得前面要防止极端条件
5. size–

好了船新代码:

public class MyLinkedNode
    {
        public int val;
        public MyLinkedNode next;

        public MyLinkedNode(int val){
            this.val = val;
        }
    }

    public class MyLinkedList
    {
        //虚假头节点
        public MyLinkedNode StartHead;

        public int size;

        public MyLinkedList()
        {
            StartHead = new MyLinkedNode(0);
            size = 0;
        }

        public int Get(int index)
        {
            //不合法 
            if(index < 0 || index >size -1)
                return -1;
            

            //从头结点开始遍历
            MyLinkedNode curNode = StartHead.next;
            while(index != 0){  //符合index==0的情况
                curNode = curNode.next;
                index--;
            }

            return curNode.val;
        }

        public void AddAtHead(int val)
        {
            MyLinkedNode addNode = new MyLinkedNode(val);
            //先让新的指向 目标节点
            addNode.next = StartHead.next;
            StartHead.next = addNode;
            size++;
        }

        public void AddAtTail(int val)
        {
            MyLinkedNode addNode = new MyLinkedNode(val);
            //找到末尾节点
            MyLinkedNode curNode = StartHead;
            while(curNode.next != null){
                curNode = curNode.next;
            }
            curNode.next = addNode;
            size++;

        }

        public void AddAtIndex(int index, int val)
        {
            //不合法 
            if(index >size)
            {
                return;
            }
            //这里如果小于零 不应该返回 而是插入头结点  
            if(index < 0)
            index = 0;   

            //找到第n个节点
            MyLinkedNode addNode = new MyLinkedNode(val);
            MyLinkedNode curNode = StartHead;
            while(index != 0){
                curNode = curNode.next;
                index--;
            }
            addNode.next = curNode.next; //添加的节点的下一个指向n个节点
            curNode.next = addNode;
            size++;
        }

        public void DeleteAtIndex(int index)
        {
            //不合法 
            if(index < 0 || index >size -1)
                return;

            MyLinkedNode curNode = StartHead;
            
            while(index != 0){
                curNode = curNode.next;
                index--;
            }
            curNode.next = curNode.next.next;
            size--;
        }
    }

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

要注意几个点一个是插入的时候按照需求 index<0 并不是不合法而是直接插入头结点。

tags: #算法