203.移除链表元素
题目链接 | 文档讲解 |视频讲解 : 链接
1.思路：
需要分情况讨论：删除的是头元素 删除的是非头元素
删除头元素，需要将头元素的下一个节点设置为新的头元素
删除非头元素，得知道当前元素以及当前元素的下一个节点，需要将前一个节点的指针指向当前元素的下一个数据
2.代码：
public ListNode removeElements(ListNode head, int val) {
//删除的是头元素的情况,
// 1.需要判断head!=null,因为我们要比较首元素的值，避免出现空指针
// 2.不可使用if, eg：7-7-7-7 val=7,使用if在这种情况下就会漏判断
while(head!=null && head.val==val){
head=head.next;
}
//指向头结点，充当前置节点
ListNode cur=head;
//需要判断当前元素以及下一个元素不为空，因为我们需要删除的其实是下一个节点
while (cur!=null && cur.next!=null){
if(cur.next.val==val){
//前置节点指向下下一个节点
cur.next=cur.next.next;
}else {
//指向下一个节点
cur=cur.next;
}
}
//返回的是链表的入口
//不能返回cur，它只是一个辅助指针，最后可能指向null,并不能代表整个链表
return head;
}1.思路2：
定义一个pre虚拟指针，指向头结点
定义一个cur指针，用于遍历数组，寻找符合条件的数据，并且它一开始指向的是pre,实际要删除的数据是cur.next
指向pre,这样删除头结点和删除非头结点的操作保持一样
2.代码
public ListNode removeElements(ListNode head, int val) {
//定义一个前置节点
ListNode pre=new ListNode();
//前置节点的指针指向头节点
pre.next=head;
//当前节点指向前置节点
ListNode cur=pre;
//为什么不判断cur,因为在这个结构下cur不会为null,因为初始值是虚拟头节点，且每次循环都可以保证cur!=null
//我们其实关注的是cur.next，而不是cur
while(cur.next!=null){
if(cur.next.val==val){
cur.next=cur.next.next;
}else{
cur=cur.next;
}
}
//返回链表的入口,即虚拟节点的下一个
return pre.next;
}707.设计链表
题目链接 | 文档讲解 |视频讲解：链接
1.思路：
- 定义了一个虚拟节点DummyHead，统一新增和删除操作
- index是从0开始的，它指的是第一个有效节点，不包含虚拟节点
- 在index位置新增和删除元素时，需要找到的操作元素的前一个元素，我们遍历寻找的时候是从虚拟节点开始的，所以index-1处就是前一个元素，注意链表size的变化
①向头部添元素：新节点指针指向真实头节点，虚拟头节点指针指向新新节点
②向index（从0开始）位置添加元素：
<1>首先判断下标的有效性 (链表有效区间 [0，size-1],但是插入元素时，=size是有效区间相当于尾部插入元素）无效区间 <0 || >size））
<2>定义一个指针cur,for循环（[0,index-1]）找到index-1的位置，节点指针变更
<3>【注】size++
③向尾部添加元素:
<1>定义一个指针cur,找到尾部节点 while循环判断的是（cur.next!=null）
<2>修改节点的指针
<3>size++
④删除index（从0开始）位置元素:
<1>先判断index的有效性（链表有效区间 [0,size-1]）
<2>循环遍历到index-1的位置，指针进行交换
<3>size--
2.代码：
class MyLinkedList {
//1.定义一个指针
class LinkedNode{
int val;
LinkedNode next;
LinkedNode(){}
LinkedNode(int val){
this.val=val;
}
}
//1.链表的个数
private int size;
//2.虚拟头结点
private LinkedNode head;
public MyLinkedList() {
this.size = 0;
//创建虚拟节点，真实头结点是head.next
this.head = new LinkedNode(0);
}
//获取链表中某个元素 index从0开始，且指向的是有效的链表节点，不包含虚拟节点
public int get(int index) {
//先判断下标是否是有效的,下标是从0开始的，所以链表的长度是size-1
if(index<0 || index>=size){
return -1;
}
//定义一个指针指向虚拟头节点
LinkedNode cur=head;
for(int i=0;i<=index;i++){
//指针后移
cur=cur.next;
}
return cur.val;
}
//在头部添加元素
public void addAtHead(int val) {
//定义一个节点
LinkedNode newNode=new LinkedNode(val);
//先将新节点的指针指向虚拟头结点的下一个即链表的真实头节点
newNode.next=head.next;
//虚拟头节点指向新节点
head.next=newNode;
size++;
}
//在尾部添加元素
public void addAtTail(int val) {
//定义一个新节点
LinkedNode newNode =new LinkedNode(val);
//定义一个指针指向头节点
LinkedNode cur=head;
//判断的是cur.next
while(cur.next!=null){
cur=cur.next;
}
//尾节点指向新节点
cur.next=newNode;
//节点个数++
size++;
}
//将一个值为 val 的节点插入到链表中下标为 index 的节点之前
public void addAtIndex(int index, int val) {
//【注】判断下标的合理性,链表的有效下标是[0,index-1],所以index=size时，相当于尾部添加元素
if(index<0 || index >size){
return;
}
LinkedNode newNode =new LinkedNode(val);
//从虚拟节点开始移动
//dummyhead -1-2-3-null 假设index=1,要在2元的前面新增节点，所以cur指针要指向的是元素1
LinkedNode cur=head;
//【注】index区间[0,index-1]
for(int i=0;i<index;i++){
cur=cur.next;
}
newNode.next=cur.next;
cur.next=newNode;
size++;
}
//删除某个元素
public void deleteAtIndex(int index) {
//判断下标的合理性
if(index<0 || index >=size){
return;
}
LinkedNode cur=head;
//因为有虚拟头节点，所以不用对index=0的情况进行特殊处理
//【注】从0开始，有效下标是[0,index-1]，找到的是其前置节点
for(int i=0;i<index;i++){
cur=cur.next;
}
//找到当前节点cur,指针指向当前节点的下一个
cur.next=cur.next.next;
size--;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/206.反转链表
题目链接 | 文档讲解 |视频讲解：链接
1.思路：反转链表，需要将原先的首节点变成尾节点，首节点的指针指向null,原先的尾节点成为首节点，中间节点的各个指针指向其上一个元素。采用 快慢指针实现
首先需要定义一个新的节点pre=null，充当慢指针
定义一个cur指针，开始指向首节点，充当快指针
这两个指针形成快慢指针，cur指针总是比pre指针快一步，pre是cur前置节点,要将cur指针的方向反转指向pre
while循环操作中，因为要修改cur指针的方向，所以我们要先将cur指向的下一个节点先记录下来，方便后续cur指针的后移，
在进行翻转,慢指针先后移,快指针在后移
最终返回pre，因为我们返回的是链表的入口，此时cur指向了null,而pre才是指向反转链表后的首节点
2.代码：
public ListNode reverseList(ListNode head) {
//1.定义一个新节点，充当慢指针
ListNode pre =null;
//定义cur指针，充当快指针
ListNode cur=head;
while(cur!=null){
//记录当前节点的下一个，方便下面cur的后移
ListNode next =cur.next;
//指针指向前置节点，指针反转
cur.next=pre;
//pre先指向cur,不可与下一步调转，调转后，快慢指针指向了同一个节点
pre=cur;
//cur后移，指向当前节点的下一个
cur=next;
}
//返回链表的入口，此时cur指向null,pre指向原链表尾节点，也就是反转后的首节点
return pre;
}总结：链表中，移除某个元素或者添加某个元素，新增一个虚拟头结点来统一操作，我们需要找到的是其前置节点，注意链表个数的变化，循环的判断条件
反转操作：采用快慢指针