做题总结 707. 设计链表

leetcode中单链表节点的默认定义

class ListNode {int val;ListNode next;//无参public ListNode() {}//有参:1public ListNode(int val) {this.val = val;}//有参:2public ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}

如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值。

我的尝试

请注意这段代码是错的，请勿参考

错误分析：
① 题目 “你可以选择使用单链表或者双链表，设计并实现自己的链表。” 是使用力扣官方给的单链表和双链表，然后设计实现自己的链表MyLinkedList 。单链表为 ListNode。
② MyLinkedList 中使用 ListNode类。
③ 添加一个变量 size，记录 MyLinkedList 中节点的个数。
④ 【问题】java中 this 指针可以更改指向吗？
⑤ MyLinkedList myLinkedList; myLinkedList.addAtHead(1); 这样是没法调用的，会报错，《might not have been initialized》
⑥ 下文代码中的 this==null 也是多余的，IDEA上说《Condition ‘this == null’ is always ‘false’》。我分析是因为this是 java虚拟机给每个对象分配的，代表当前对象。而对象一定是需要在堆中new出来的。如果只是MyLinkedList myLinkedList; 其实这个变量只是在栈中定义，堆中并没有对象。
⑦ 虚拟头节点/哑节点/dummy head，是为了方便增删。
⑧ 力扣中定义的class是可以加属性的。

//代码是错的，请勿参考。
class MyLinkedList {int val;MyLinkedList next;public MyLinkedList() {this.val = 0;this.next = null;}public int get(int index) {if(index < 0) return -1;//下标无效//this有可能为空吗？int count=0;MyLinkedList h = this;while(h!=null) {if(count == index) {return h.val;}h = h.next;count++;}return -1;}public void addAtHead(int val) {MyLinkedList newhead = new MyLinkedList();newhead.val = val;newhead.next = this;this = newhead;}public void addAtTail(int val) {MyLinkedList newnode = new MyLinkedList();newnode.val = val;newnode.next = null;if(this == null) {this = newnode;} else {MyLinkedList temp = this;while(temp.next != null) {temp = temp.next;}temp.next = newnode;}}public void addAtIndex(int index, int val) {//链表为空：index再合法也没用//index不合法//index超过链表长度//加在中间//加在末尾if(this == null) return;if(index < 0) return;MyLinkedList newnode = new MyLinkedList();newnode.val = val;newnode.next = null;//哑节点MyLinkedList newh = new MyLinkedList();newh.next = this;//tempMyLinkedList temp = newh;//计数int count=0;while(temp.next!=null) {if(count == index) {newnode.next = temp.next.next;temp.next = newnode;return;}count++;temp = temp.next;}if(index == count) {temp.next = newnode;}return;//index超过链表长度}public void deleteAtIndex(int index) {}
}

正确运行的代码（java）

分析：
① get、addAtIndex、 deleteAtIndex中的 for循环查找 index 用的是同一套逻辑，for循环之后，temp所在的位置是 目标为index节点的前一个。
② addAtHead、addAtTail 可以合并到addAtIndex中。
③ size这个变量很巧妙得同时考虑到了，链表为空和 index大于链表长度的情况。

class MyLinkedList {int size;ListNode head;//注意这里是单链表节点 ListNode//虚拟头节点public MyLinkedList() {this.size = 0;head = new ListNode(0);//注意这里是单链表节点 ListNode}public int get(int index) {if(index < 0 || index >=size) {return -1;}ListNode temp = this.head;for(int i=0; i<index; i++) {temp = temp.next;}return temp.next.val;//这里}public void addAtHead(int val) {addAtIndex(0,val);}public void addAtTail(int val) {addAtIndex(size,val);}public void addAtIndex(int index, int val) {if(index < 0 || index > size) {return;}//size避免了链表为空，index大于链表长度的情况ListNode node = new ListNode(val);ListNode temp = this.head;for(int i=0; i<index; i++) {temp = temp.next;}node.next = temp.next;temp.next = node;size++;}public void deleteAtIndex(int index) {if(index < 0 || index >= size) {return;}ListNode temp = this.head;for(int i=0; i<index; i++) {temp = temp.next;}temp.next = temp.next.next;size--;//这里}
}class ListNode {int val;ListNode next;//无参public ListNode() {}//有参:1public ListNode(int val) {this.val = val;}//有参:2public ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}