代码随想录第四天（203、707）
文章目录
- 一、链表知识
- 203. 移除链表元素
- 提交
- 看答案之后的豁然开朗
- 707. 设计链表
- 完全不会，看完答案后改的
一、链表知识
1、链表在内存中的存储不是连续的
意思是这个链表的其实节点是2，终止节点是7
2、链表和数组的对比
数组的长的是固定的，不能改变
链表的长度不固定
3、链表的定义（代码）
public class ListNode {
// 结点的值
int val;
// 下一个结点
ListNode next;
// 节点的构造器(无参)
public ListNode() {
}
// 节点的构造器(有一个参数)
public ListNode(int val) {
this.val = val;
}
// 节点的构造器(有两个参数)
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
203. 移除链表元素
第一次提交失败，原因是没有考虑清楚：
①题目给的头节点是指的真正链表的头节点，还是一个指向真正头结点的虚拟节点
②返回值写成head出错，因为如果整个链表都是要删除的，head节点也就被删除了，应该返回的是虚拟节点的nex
t③给出的测试用例中有一种是链表为空的情况，而我写的temp=head.next;此时链表为空，也就是head是null，但是我又让temp存储head的next值，所以出现空指针异常的错误。因为此时head节点都不存在，而且注意，这里报的错是执行出错，而不是编译出错，也就是不是书写的问题。这里应该让temp指向pre的next值，因为pre是肯定存在的
④看完答案后，发现应该创建一个虚拟指针一直指向创建的虚拟节点，这样返回值可以直接返回这个虚拟节点的next值，比较方便。如果没有这个固定的指针，返回值想写return head是不对的，解释类似于前面的③
提交
**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode first=new ListNode(0,head);
ListNode pre=first;
ListNode temp=pre.next;
while(temp!=null){
if(temp.val==val){
pre.next=temp.next;
}else{
pre=pre.next;
}
temp=pre.next;
}
pre.next=null;
return first.next;
}
}
看答案之后的豁然开朗
1、整个链表题分为两种情况，一种是创建虚拟节点，这样能够让头结点的删除和其他节点的删除操作一样；另一种是不设置虚拟节点，这种情况就要先对头节点进行处理，这是分为两步，第一步先检查头结点的值，如果是要删除的值，让头节点后移，直到移动到链表结尾或者发现第一个不是要删除值的节点；第二步是，判断此时的头结点的next是不是空，如果是空，代表此时链表为空，直接返回，若不是空，在进行后面节点的删除操作
2、答案里面新建的虚拟节点的值写的是-1，不是0
3、答案中一共给了三种方法，一种是添加虚拟节点的，一种是不添加虚拟节点，但有pre，还有一种是既没有虚拟节点，也没有pre的，这种就是用到了temp指向头节点，然后用了temp.next.next
707. 设计链表
不知道怎么做，因为不知道怎么在方法里定义虚拟头节点，然后怎么样让这个虚拟头节点指向链表的头节点。而且还要判断index的值是否无效，这就要看链表长度是否小于等于index，但是链表长度又不知道。
看答案发现，这些问题定义在这个类中的一个方法中，这个方法创建了头节点、尾节点，还需要特别注意，就是将这两个节点的指针进行关联，不然后面会报空指针异常，因为初始化的两个节点默认带的两个指针都是ListNode这个引用类型，所以初始化值都是null。关联的代码是：head.next=tail;
tail.prev=head;
另外，有一个忽视的点：for循环
for (表达式1; 表达式2; 表达式3)
{
语句;
}
过程：
求解表达式1。
求解表达式2。若其值为真，则执行 for 语句中指定的内嵌语句，然后执行第3步；若表达式2值为假，则结束循环，转到第5步。
求解表达式3。
转回上面第2步继续执行。
循环结束，执行 for 语句下面的语句。
完全不会，看完答案后改的
【注意】
①再添加完节点后，方法里面要有对size++的调整
②删除操作记得size - -
class ListNode{//定义链表节点类
int val;
ListNode next;
ListNode prev;
public ListNode(){
}
// public ListNode(int val,ListNode next,ListNode prev){
// this.val=val;
// this.prev=prev;
// this.next=next;
// }
public ListNode(int val){
this.val=val;
}
}
class MyLinkedList {
int size; //这一部分先定义类的属性，可以在这里进行赋初值操作
ListNode head;
ListNode tail;
public MyLinkedList() {//空参构造器中的意味着只要创建一个这个类的对象
//就会造相应的头、尾节点，为了防止后面的节点的next和prev出现null从而
//在赋值过程中出现空指针异常，这里要将两个节点的next和prev关联上
size=0;
// ListNode head=new ListNode(-1,null,null);
head=new ListNode(-1);
tail=new ListNode(-1);
head.next=tail;
tail.prev=head;
}
public int get(int index) {//其实这个方法在看答案的过程中发现
//分了两种情况，当时以为是可写可不写的，作用只是加快了查找速度，
//但后来发现，其实分两种情况就避免了空指针异常的情况
if(index<0||index>size-1){
return -1;
}
// ListNode c=new ListNode();
ListNode c;
c=head;
for(int i=0;i<=index;i++){
c=c.next;
}
return c.val;
}
public void addAtHead(int val) {
// ListNode addone=new ListNode(val,null,null);
ListNode addone=new ListNode(val);
// addone.next=head.next;
// head.next.prev=addone;
// head.next=addone;
// addone.prev=head;
addAtIndex(0,val);
}
public void addAtTail(int val) {
// ListNode addone=new ListNode(val,null,null);
ListNode addone=new ListNode(val);
// ListNode c=head;
// while(c.next!=null){
// c=c.next;
// }
// c.next=addone;
// addone.prev=c;
addAtIndex(size,val);
}
// public void addAtIndex(int index, int val) {
// if(index>size-1){
// return;
// }else if(index==size-1){
// addAtTail(val);
// }else if(index<=0){
// addAtHead(val);
// }else{
// // ListNode addone=new ListNode(val,null,null);
// ListNode addone=new ListNode(val);
// ListNode c=head;
// for(int i=0;i<index;i++){
// c=c.next;
// }
// c.next.prev=addone;
// addone.next=c.next;
// c.next=addone;
// addone.prev=c;
// }
// }
public void addAtIndex(int index, int val) {
if(index>size){
return;
}
int num=Math.max(0,index);
ListNode c=head;
for(int i=0;i<num;i++){
c=c.next;
}
ListNode addone=new ListNode(val);
addone.next=c.next;
c.next.prev=addone;
c.next=addone;
addone.prev=c;
size++;//记得！！！！！！
}
// public void deleteAtIndex(int index) {
//这个算法是第一次写的，运行时老是出错
// if(index<0||index>size-1){
// return;
// }
// ListNode c=head;
// for(int i=0;i<index;i++){
// c=c.next;
// }
// c.next=c.next.next;
// c.next.next.prev=c;//老是提示prev前面的对象是null
//出现了空指针异常，特殊情况就是要删除最后一个节点等情况时，后面
//没有结点了，而分两种情况就可以避免寻找在index靠后时还寻找
//c.next.next.prev，而是往前找
// size--;
// }
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
ListNode pred, succ;
if (index < size - index) {
pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
succ = pred.next.next;
} else {
succ = tail;
for (int i = 0; i < size - index - 1; i++) {
succ = succ.prev;
}
pred = succ.prev.prev;
}
size--;
pred.next = succ;
succ.prev = pred;
}
}