LeetCode_Subject707

lpc0828

设计链表
通过这个题目对数据结构 有一丝丝理解 数据结构中的size 在对数据结构的增删改查过程 起到了一个很重要的作用
自己在写的过程中 没有想到用size 拖延了很多天  写了很多的if 代码非常非常的乱 随便改一个if 牵一发而动全身  满足了这个就不能满足别的地方的条件了
很笨很笨，这里我只写自己的想法

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开始
分析题目
给头部增加元素 给尾部增加元素 给指定下标增加元素  这三个可以合并成为最后一个 给指定下标增加元素链表
增加元素做的事情是找到指定位置 增加一个新元素 它的上一个位置保存它 它的下一个位置保存这个位置之前的元素链表
删除元素做的事情是找到指定位置 删除当前位置元素 把当前位置元素的下一个元素 放到这个位置链表
查询指定位置的元素 找到位置取出即可
size 可以省略很多很多复杂的判断 你要找到指定的位置去操作 这个位置有可能是不存在的 这个位置找的时候 你只能通过写一个temp数字来记录是不是到了位置很繁琐很繁琐，如果位置不存在 直接return 如果位置存在 直接循环到指定的位置取出元素进行操作 简直不要太妙
1.头部  这个头部 需要做的是 保存size 重点是保存size
链表类里面有一个属性是size 第一个节点永远为0 这是为了让头节点跟中间节点、尾节点一样 不需要单独处理
2.指定下标增加元素先++size; 循环判断循环次数不能大于index
2.1 开头size==1  index为0 不进入循环 new 一个新的节点  当前元素是0 下一个元素是当前的第一个元素 也就是0-1 我们插入一个2 就是把当前元素的下一个元素指向2 然后把2的下一个元素指向1
2.2 中间
index不为0 可以进入循环 比如是这个0-1-3 第0个元素是1 第1个元素是3 我们要在下标1的位置加入2  循环一次 当前元素是1 把1的下一个指向2 2的下一个指向3
2.3 尾部
index不为0 进入循环 比如是0-1-2  第0个元素是1 第1个元素是2 我们要插入的位置是2 size也是2 刚好可以插入 index=2 循环三次 当前元素就是2 new 一个新节点3出来  3的下一个元素变成2的下一个元素 为null 2的下一个元素变为3
3.取指定位置下的元素
通过size判断 如果下标不存在 直接return-1
取指定位置的元素比如0-1-2-3 要取第0个元素 index为0 不进入循环直接返回0的下一个元素1
要取第1个元素 index为1循环一次 取出1的下一个元素2
4.删除元素
先判断size 下标不存在 就不做操作
--size;
删除元素从头开始查
4.1删除头部
0-1-2 删除下标0的元素 先判断index为0 不进行循环 也就是把 0 直接指向到2
4.2删除中间
0-1-2-3 删除下标1的元素 先判断index为1 循环一次 到1的位置 直接把1指向到2的下一个位置3
4.3删除尾部
0-1-2 删除下标1的元素 先判断index为1 循环一次 到1的位置 直接把0指向到2 的下一个位置null
打完收工



size 是数据结构中的核心核心核心 切记