代码随想录：链表
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，数据域（存数据）和指针域（存指向下一个节点的指针），最后一个节点指针域指向NULL。链表的入口叫头节点head
单链表：节点只能指向下一个节点next A->C->D->E->NULL
双链表：每个节点有两个指针域，一个指向下一个节点一个指向上一个节点，即可以向前查询也可以向后查询 NULL<-A<=>C<=>D<=>E->NULL
循环链表：首尾相连
链表的存储方式，链表在内存中是不连续分布的，链表通过指针域的指针连接内存中各个节点
链表的定义：
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
链表的操作：A->C->D->E->NULL删除节点D，将C的next指向E即可
A->C->D->E->NULL将F添加到CD中间，C的next指向F，F的next指向E
链表的长度是可以不固定的，适合频繁增加删除较少查询的情况
判断链表是否有环可用双指针，分别定义fast和slow指针，fast每次移动两步slow每次移动一步，若有环则二者一定会在环中相遇（都进入环中后二者相对距离每次移动改变量为1因此一定可以相遇）
寻找环的入口：假设从头到环入口节点数x，入口到相遇点节点数为y，相遇点到环入口节点数为z，二者相遇时slow指针移动节点数为x+y，fast指针移动节点数为x+y+n(y+z)，n为在环内移动的圈数。由于fast一次移动两步，slow一次移动一步，因此可得等式2(x+y)=x+y+n(y+z)，化简后为x+y=n(y+z)，x=(n-1)(y+z)+z。当n=1时，有x=z，此时令一个指针从头结点出发，另一个指针从相遇点出发，每次都只移动一步则二者相遇点就是环的入口，n不为1时相遇前环内的指针额外走n-1个环的距离，最终相遇点不会改变。
力扣203：移除链表元素
public class Solution {
public ListNode RemoveElements(ListNode head, int val) {
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode cur=dummy;
//建立虚拟头节点，将后续操作统一，否则需要特殊处理头节点
while(cur.next!=null){
if(cur.next.val==val){
cur.next=cur.next.next;
//删除操作，指针指向下个指针指向的节点
}
else{
cur=cur.next;
}
}
return dummy.next;
//返回的时候去掉虚拟头节点
}
}
力扣707：设计链表
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/design-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
public class LinkedNode{
public int val;
public LinkedNode next;
public LinkedNode(int val){
this.val=val;
this.next=next;
}
}//定义链表结构体
public class MyLinkedList {
public int size;
public LinkedNode head;
public MyLinkedList() {
size=0;
head=new LinkedNode(0);
//初始化链表
}
public int Get(int index) {
if(index>(size-1)||index<0){
return -1;
//查不到的元素返回-1
}
LinkedNode cur=head;
while(index-->=0){
cur=cur.next;
//因为有虚拟头节点要多循环一次才是真正的位置
}
return cur.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>size){
return;
//index=size就是加在末尾后面的空位，加上虚拟头节点链表长度实际为size+1
}
LinkedNode cur=head;
LinkedNode temp=new LinkedNode(val);
while(index-->0){
cur=cur.next;
}
temp.next=cur.next;
cur.next=temp;
size++;
}
public void DeleteAtIndex(int index) {
if(index>=size||index<0){
return;
//index=size时末尾为空无法删除
}
LinkedNode cur=head;
while(index-->0){
cur=cur.next;
}
cur.next=cur.next.next;
size--;
}
}
力扣206：反转链表
//双指针法，cur指向头节点，pre作为新链表的头节点，temp保存cur.next在执行完将cur.next指向pre后将pre指向cur，cur指向temp，以此完成cur和pre的移动
public 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;
}
}
//递归法
public class Solution {
public ListNode ReverseList(ListNode head) {
return Reverse(null,head);
}
public ListNode Reverse(ListNode pre,ListNode cur){
//定义反转操作将cur.next指向pre
if(cur==null){
return pre;
//结束条件，返回反转后的链表
}
ListNode temp=cur.next;
cur.next=pre;
return Reverse(cur,temp);//使用递归进行循环
}
}
力扣19：删除链表的倒数第n个节点
public class Solution {
public ListNode RemoveNthFromEnd(ListNode head, int n) {
ListNode nHead=new ListNode(0);
nHead.next=head;
//虚拟头节点，这样做就不需要讨论删除头结点的特殊情况
ListNode left=nHead;
ListNode right=nHead;
//双指针
while(n>=0)
{
right=right.next;
n--;
//快指针先走出n+1步
}
while(right!=null)
{
left=left.next;
right=right.next;
//同时移动快慢指针，这样当快指针指向null时慢指针恰好指在倒数第n+1个元素
}
left.next=left.next.next;
//删除慢指针指向的下一个元素
return nHead.next;
//有虚拟头节点因此在此处返回值中应删除该虚拟头节点
}
}
力扣142：环形链表II
public class Solution {
public ListNode DetectCycle(ListNode head) {
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
//判断有没有环
if(slow==fast){
ListNode n1=fast;
ListNode n2=head;
while(n1!=n2){
n1=n1.next;
n2=n2.next;
//成环了就从头和相遇点开始一步步找新的相遇点即为环入口
}
return n2;
}
}
return null;
//没成环返回null
}
}
//（代码第一次写完超时了，写的判断入口的部分没有放到循环内所以出现死循环）
