链表(二)——设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性: 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

提示：

• 所有val值都在 [1, 1000] 之内
• 操作次数将在 [1, 1000] 之内
• 请不要使用内置的 LinkedList 库

单链表

思路

- 定义单链表的结构

class Node {
    
        int val; // 节点上存储的元素
        Node next;    // 指向下一个节点的指针
        Node(int val) {
      // 节点的构造函数
            this.val = val;
        }
    int size; // 定义结点的个数
    Node head; // 定义头节点

- get(index)

• 判断index是否在存在的节点之内
• 通过遍历，取出节点索引的值

   public int get(int index) {
    
        // 判断index是否在存在的节点之内
        if (index < 0 || index >= size || head == null) {
    
            return -1;
        }
        Node temp = this.head;
        // 通过遍历，取出节点索引的值
        for (int i = 0; i < index; i++) {
    
            temp = temp.next;
        }
        return temp.val;
    }

- addAtHead(val)

• 插入新节点作为新的头节点
• 节点数增加1
  

    public void addAtHead(int val) {
    
        Node node = new Node(val);
          // 新结点指向原头结点的值
        node.next = this.head;
         // 新节点作为新的头节点
        this.head = node;
         // 节点数增加1
        size++;
    }

- addAtTail(val)

• 是否有节点，若无则增加的是头节点
• 找到最后一个节点，指向新结点的值
• 新结点指向null

   public void addAtTail(int val) {
    
       // 是否有节点，若无则增加的是头节点
        if (size == 0) {
    
            this.head = new Node(val);
            head.next = null;
            size++;
        }else {
    
            Node temp = this.head;
            while (temp.next != null) {
    
                temp = temp.next;
            }
            // 找到最后一个节点，指向新结点的值
            // 新结点指向`null`
            Node tail = new Node(val);
            tail.next = null;
            temp.next = tail;
            size++;
        }
    }

- addAtIndex(index,val)

• 当index > size,索引越界，不能插入节点
• 当index < 0,新插入的节点为头节点
• 当index = size,新插入的节点为最后一个节点
• 找出目标节点的前一个结点，后面的节点加1

public void addAtIndex(int index, int val) {
    
     // 当`index > size`,索引越界，不能插入节点
        if (index > this.size) {
    
            return;
        }
        // 当`index < 0`,新插入的节点为头节点
        if (index <= 0) {
    
            addAtHead(val);
            return;
        }
        // 当`index = size`,新插入的节点为最后一个节点
        if (index == this.size) {
    
            addAtTail(val);
            return;
        }
       // 找出目标节点的前一个结点
        Node temp = this.head;
        for (int i = 0; i < index - 1; i++) {
    
            temp = temp.next;
        }
        // 该位置插入新节点，后面的节点加1
        Node insertNode = new Node(val);
        insertNode.next = temp.next;
        temp.next = insertNode;
        size++;
    }

- deleteAtIndex(index)

• 判断index是否在存在的节点之内
• 头节点分开讨论
• 通过遍历，取出节点索引的值并删除
• 节点数减1
  

public void deleteAtIndex(int index) {
    
       // 判断`index`是否在存在的节点之内
        if (index < 0 || index >= this.size) {
    
            return;
        }
        // 头节点分开讨论
        if (index == 0) {
    
            if (size != 1) {
    
                Node temp = this.head.next;
                this.head =temp;
                size--;
                return;
            }else {
    
                this.head = null;
                size--;
                return;
            }
        }
        Node temp = this.head;
        // 通过遍历，取出节点索引的值并删除
        for (int i = 0; i < index - 1; i++) {
    
            temp = temp.next;
        }
        Node deleteNode = temp.next;
        temp.next = deleteNode.next;
        // 节点数减1
        size--;
    }