1.题目
2. 思路分析
1.我们要设置一个虚拟头节点,因为这个虚拟头节点对于增加节点操作和删除节点操作都很方便。
2.仔细读题,题目中说链表中的节点下标是从0开始的。也就是说第一个节点下标为0。
3.增加节点和删除节点的操作我们都要获取到它前一个的节点。
4.对于边界条件的判断,我们都假设index=0的情况来判断。比如添加节点的边界条件判断,我们拿addAtIndex(index=0)去做。
5.这道题测试用例有个bug,就是AddAtIndex这个方法,测试用例可能会传一个负数索引进来,这种情况下,我们将负索引节点插入到第一个节点。
3.构造节点
class ListNode {int val;ListNode next;public ListNode() {}public ListNode(int val) {this.val = val;}
}
4.MyLinkedList类实现
class MyLinkedList {int size;ListNode head; //虚拟头节点public MyLinkedList() {size = 0;head = new ListNode(0);}public int get(int index) {if (index > this.size - 1 || index < 0)return -1;else {int count = 0;ListNode cur = head.next;while (count < index) {cur = cur.next;count++;}return cur.val;}}public void addAtHead(int val) {ListNode addNode = new ListNode(val); //新建要插入的节点addNode.next = head.next;head.next = addNode;size++;}public void addAtTail(int val) {ListNode addNode = new ListNode(val);ListNode cur = head;//cur要到最后一个节点while (cur.next != null) {cur = cur.next;}cur.next = addNode;size++;}public void addAtIndex(int index, int val) {if (index > size) {return; //什么也不用干}//如果索引小于0,则插入到头节点if (index < 0) {index = 0;}//找到要插入的位置(即cur指向 index对应节点的前一个节点)ListNode cur = head;int count = 0;while (index > 0) {cur = cur.next;index--;}//创建要插入的节点ListNode addNode = new ListNode(val);addNode.next = cur.next;cur.next = addNode;size++;}public void deleteAtIndex(int index) {if (index < 0 || index > size - 1) {return;}//找到要删除的节点的前一个节点,即cur指向要删除的节点的前一个节点ListNode cur = head;while (index > 0) {cur = cur.next;index--;}cur.next = cur.next.next;size--;}
}