203.移除链表元素
题意：删除链表中等于给定值 val 的所有节点。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
看到题目第一想法
最直观的想法，分情况讨论是否是头节点。是头节点，直接改变头结点位置。不是头结点，就将应删除节点上一个节点直接指向下下个节点。
注意：操作节点前要判断是否为空。
//伪代码
//移除头节点
//判断头节点不为空，不然就是操纵空指针了，编译报错
//if(head!=null&&head->val==target)不对头节点应持续移除，例如1 1 1 1 1 100 移除1
while(head!=null&&head->val==target)
head=head->next
cur=head;//临时指针指向头节点 定义临时指针用来遍历，不能用头结点遍历，最后返回不了应该返回的头节点
while(cur!=null &&cur->next!=null )//cur不能为空 cur->next也不为空 因为我们要取值和target对比,不然就是操纵空指针了，编译报错
if(cur->next==target) //cur的下一个节点应删除
cur->next=cur->next->next//cur的下一个节点为当前cur的下一个下一个节点
else cur=cur->next
//必须放else cur当前节点前面判断过不是val;只有cur下一个经过if判断也不是才能将临时指针后移
/* 若 if(cur->next==target)
cur->next=cur->next->next/
cur=cur->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) {
//不采用虚拟头节点
while(head!=null && head.val==val){
head=head.next;
}
ListNode cur=head;
while(cur!=null&&cur.next!=null){//cur!=null要加上 不判断的话 cru=null那么不存在next
if(cur.next.val==val){
cur.next=cur.next.next;
}else{cur=cur.next;}
}
return head;
}
}
学习之后
发现通过引入虚拟节点可以不用单独分出头节点来讨论。
这里来给链表添加一个虚拟头结点为新的头结点，此时要移除这个旧头结点元素1。
这样就可以使用和移除链表其他节点的方式了，最后在题目中，return 头结点的时候，别忘了 return dummyNode->next;， 这才是新的头结点。
//伪代码
//虚拟头节点dummy head 统一链表操作操作
dummy head=new();
dummyhead->next=head;
cur=dummyhead//不等于dummyhead->next 因为要删的是cur->next,当前是head
while(cur->next!=null)
if (cur->next->val==target)
cur->next=cur->next->next;
else cur=cur->next
return dammyhead->next
/**
* 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 dummyhead= new ListNode (1,head);
ListNode cur = dummyhead;
while(cur.next!=null){
if(cur.next.val==val){
cur.next=cur.next.next;
}else {cur=cur.next;}
}
return dummyhead.next; }
虚拟头节点，cur临时指针=虚拟头节点。
707.设计链表
题意：
在链表类中实现这些功能：
? get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
? addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
? addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
? addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
? deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
看到题目第一想法
采用虚拟头节点来对五种操作进行编码。
//伪代码
/**链表常见操作
1获取第n各节点的值（节点地址从0开始）
2头部插入节点
3尾部插入节点
4第n个节点前插入节点
5删第n个节点*/
//本题均采用虚拟头节点
//1
cur =dummyhead.next//遍历链表一定新建临时指针不能直接操作头指针 因为最后要返回头指针
while(n){//循环条件带入边界验证是否满足 n=0头节点 跳出循环； n=1第二个节点
cur=cur.next
n--
}
return cur.val
//2
ListNode newNode= new ListNode();
newNode.next=dummyhead.next;//先后后前
dummyhead.next=newNode;
return dummyhead.next
//3
cur=dummyhead
while(cur.next!=null){
cur=cur.next
}
ListNode newNode =new ListNode()
cur.next=newnode
//4 在第n个节点前插入 即 cur n-1 cur.next n 这两个节点之间操作 第n个节点为cur.next
cur=dummyhead
while(n--){//举极端例子验证
cur=cur.next
}
newNode.next=cur.next;
cur.next=newNode
size++
//5 n为cur.next 才能删掉 直接cur.next=cur.next.next; 写之前先想明白 n是cur.next
cur=dummyhead
while(n){//极端例子 只有一个节点 删除第0个节点
cur=cur.next
n--
}
cur.next=c
size--
//写了之后发现报错查了半天发现忘了更新size大小了
class ListNode{
int val ;
ListNode next;
public ListNode(){};
public ListNode(int val){
this.val=val;
}}
class MyLinkedList {
int size;//记录链表大小
ListNode dummyHead;//虚拟头节点
public MyLinkedList() {//初始化
dummyHead=new ListNode(-1);
size=0;//只有虚拟头节点所以大小为0
}
public int get(int index) {
if(index<0||index>=size){
return -1;
}else{
ListNode cur=dummyHead;//所有临时指针均指向虚拟头节点
while(index!=0){
cur=cur.next;
index--; }
return cur.next.val;
}
}
public void addAtHead(int val) {
ListNode newNode=new ListNode(val);
newNode.next=dummyHead.next;
dummyHead.next=newNode;
size++;
return ;
}
public void addAtTail(int val) {
ListNode newNode= new ListNode(val);
ListNode cur=dummyHead;
while(cur.next!=null){
cur=cur.next;
}
cur.next=newNode;
size++;
return;
}
public void addAtIndex(int index, int val) {
if(index>size){return;}
ListNode newNode=new ListNode(val);
ListNode cur= dummyHead;
if(index<0){
addAtHead(val);
return ;
}
while(index--!=0){
cur=cur.next;
}
newNode.next=cur.next;
cur.next=newNode;
size++;
return;
}
public void deleteAtIndex(int index) {
if(index<0||index>=size){//地址0开始最多size-1
return ;}
ListNode cur=dummyHead;
while(index--!=0){//JAVA不能直接写while(index)
cur=cur.next;
}
cur.next=cur.next.next;
size--;
return ;}
}
/**
* 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);
*/
针对第n个数进行操作，让cur.next=该数。
206.反转链表
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
看到题目第一想法
只需要改变链表的next指针的指向，直接将链表反转，无需增加删除节点。
针对此题需要两个指针一个指当前节点，一个指当前节点的前节点，用来转换指针方向，还需要一个临时节点来寄存原来节点的下一个节点，用来移动前面两个定位的节点。
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。
//伪代码
//双指针pre改方向 cur 遍历
//初始化 共需要三个临时指针
cur=head
pre=null
while(cur==null){//终止条件cur=null 不能是null 空指针异常 也不能是cur.next=null 此时pre不是头节点，寻找不变量
//一开始 pre=null cur=head,最后pre=head,cur=null
temp=cur.next;//先保存原来下一个节点
cur.next=pre;
pre=cur;
cur=temp;}
return pre;
//双指针
/**
* 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 reverseList(ListNode head) {
ListNode cur=head;
ListNode pre=null;
ListNode temp;
while(cur!=null){
temp=cur.next;
cur.next=pre;
pre=cur;
cur=temp;
}
return pre;
}
}
递归法
递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。
关键是初始化的地方，可能有的同学会不理解， 可以看到双指针法中初始化 cur = head，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。
递归法本质就是自己调用自己的方法。
//递归与双指针接法一一对应
//自定义reverse函数
reverse(cur,pre)
if(cur==null){
return pre;
}
temp=cur.next;//先保存下一个节点的位置
cur.next=pre;//然后改变方向
reverse(temp,cur);//递归调用自己方法；
//输入函数reverseList（head）
reverseList(head){
return reverse(head,null)
}
//递归报错代码
/**
* 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 reverseList(ListNode head) {
return reverse(head,null);}
public ListNode reverse(ListNode cur,ListNode pre){
ListNode temp=cur.next; //报错[]不符，要先判断 cur是否为[]
cur.next=pre;
if(temp!=null){
return reverse(temp,cur);
}
return cur;}}
```//递归
/**
* 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 reverseList(ListNode head) {
return reverse(head,null);}
public ListNode reverse(ListNode cur,ListNode pre){
if(cur==null){
return pre;}
ListNode temp=cur.next;
cur.next=pre;
return reverse(temp,cur);}