力扣刷题--设计链表707

这个题目的难点：

• 确定index是什么，index的范围
• 向后遍历的次数，也就是循环的次数
• 在某处添加或者删除一个结点，需要找到它的前一个结点

单链表

首先对于创建一个链表，需要单链表结构

public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

再设计一个自己的链表
对于一个链表，有两个成员成员变量：、

1. size（记录链表长度）
2. head（一个虚拟头结点）

初始化一个链表：

//    初始化这个链表
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);  //创建一个虚拟头节点
    }

获取索引处的数值

比如上图，要找index=2时候的数值：
首先确定index的范围是否有效：if (index < 0 || index >= size)
找到index这个节点 for(int i = 0; i <= index; i++)

    //获取索引处的数值
    //获取索引处的数值
    public int get(int index) {
        //index范围： 0,size-1
        if (index >= size || index <0){
            return -1;
        }
        ListNode cur = head;
        //因为包含一个虚拟头节点 所以要多移动一位
        for (int i = 0; i <= index; i++) {
            cur= cur.next;
        }
        return cur.val;
    }

在头处加入数值

不需要进行任何判断，因为虚拟头节点一直都在。
需要注意的是插入步骤不能反了，否则会出现指针丢失，找不到下一个节点的状况。

  //也就是在head节点和第一个节点直接加入一个节点
    public void addAtHead(int val) {
        ListNode temp = new ListNode(val);
        temp.next =head.next;
        head.next = temp;
        size++;
    }

在最后加入一个数值

先找到最后一个节点：也就是cur的遍历次数：for(int i = 0; i < size ; i++)
再进行插入。

 
    public void addAtTail(int val) {
        ListNode cur = head;
        for (int i = 0; i < size; i++) {
            cur = cur.next;
        }
        ListNode temp = new ListNode(val);
        cur.next = temp;
        temp.next = null;
        size++;
    }

在索引处加入一个数值

首先需要明确的是插入的index的范围：
值得注意的是index=size这个地方可能会被遗漏，index的范围是[0,size-1]，但是插入的时候，index=size是可以的，这相当于在当前列表的最后插入了一个节点。

然后是插入步骤
比如要在index=3这个地方插入一个结点，需要先找到index=2这个地方，用i进行循环遍历，i的范围为for(int i = 0 ; i < index ; i++)
需要注意的是，在index处插入一个结点，需要找到它的前一个结点，而不是找到它这个结点。
比如下图的temp插入后就成了链表中 index = 3 的结点。
插入的顺序也需要注意一下。

	public void addAtIndex(int index, int val) {
        if (index > size){
            return;
        }
        if (index < 0){
            index = 0;
        }
        ListNode cur = head;
        //找到要插入处的前一个节点
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        ListNode temp = new ListNode(val);
        temp.next = cur.next;
        cur.next = temp;
        size++;
    }

删除索引处的元素

首先需要确定的是可以删除的index的范围：[0,size-1] （如图所示红色的index部分）
然后需要注意的是，删除一个结点，需要找到它的前一个结点，比如图中，需要删除index=2处的结点，需要找到index=1处的结点，也就是i的循环范围是for(int i = 0 ; i < index ; i ++) ，再执行删除操作，此处的删除操作很简单，就是是得cur.next = cur.next.next.

    public void deleteAtIndex(int index) {
        if (index < 0){
            return;
        }
        if (index >= size){
            return;
        }
        ListNode cur = head;
        //找到这个索引的前一个节点
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        size--;
    }

总结：
链表中需要注意的就是index的范围，每次cur遍历，cur需要遍历几次，找到什么位置。
插入的时候的步骤顺序不能反了，否则会出现找不到下一个结点的状况。