链表
链表--移除链表元素
题目：力扣题目链接
题意：删除链表中等于给定值 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
输出：[]
题解：
/**
* 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 a = new ListNode(0);
a.next=head;
ListNode cur=a;
while(cur.next!=null){
if(cur.next.val!=val){
cur=cur.next;
}else{
cur.next=cur.next.next;
}
}
return a.next;
}
}
解析：在head定义一个虚拟结点，它的next是head。定义一个指针cur指向这个虚拟节点，在cur的next不为空的前提下，遍历整个元素，如果cur的next对应的元素不是目标值，则cur指针后移,否则如果是目标值则cur.next=cur.next.next删除即可，最后返回头节点。
链表--翻转链表
题目：力扣题目链接
反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->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) {
ListNode a=null;
ListNode cur=head;
while(cur!=null){
ListNode next=cur.next;
cur.next=a;
a=cur;
cur=next;
}
return a;
}
}
解析：迭代法：定义一个空的前驱指针a,一个当前指针指向头结点，定义一个后继指针，指向当前指针的下一个元素，进行探路。当当前指针非空时，进行反转，反转方法是让当前元素指针的next指向前驱结点，然后前驱结点指针后移,当前节点指针后移，不断循环，最后返回a，反转链表成功。
链表--设计链表
题目：力扣题目链接
在链表类中实现这些功能：
-
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
-
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
-
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
-
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
-
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
题解：
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val) { this.val=val; } } class MyLinkedList { int size; ListNode head; public MyLinkedList() { size=0; head=new ListNode(0); } public int get(int index) { if(index<0||index>=size){ return -1; } ListNode cur=head; for(int i=0;i<index;i++){ cur=cur.next; } return cur.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 > size) { return; } if (index < 0) { index = 0; } size++; ListNode pre=head; for(int i=0;i<index;i++){ pre=pre.next; } ListNode newNode=new ListNode(val); newNode.next=pre.next; pre.next=newNode; } public void deleteAtIndex(int index) { if (index < 0 || index >= size) { return; } size--; ListNode pre=head; for(int i=0;i<index;i++){ pre=pre.next; } pre.next=pre.next.next; } } /** * 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); */
解析：
（1）得到指定位置的值：index在合理范围内，否则返回-1，定义当前指针指向头结点，遍历整个结点，找到目标结点前一个元素，然后指定位置的值就是cur.next.val.
(2)在指定位置添加值：判断index是否在合理的范围内，大于size返回，小于0即为0.先让整个size++，定义一个指针指向头节点，遍历整个结点，找到指定位置的前一个元素，然后创建一个新的结点，然后newNode.next=pre.next；
pre.next=newNode即可完成
(3)在头插入元素：调用(2)方法即可，addAtIndex(0, val);
(4)在尾部插入元素：调用(2)方法即可，addAtIndex(0, val);
(5)在指定位置删除元素：判断index是否合法，如果index<0或者>size直接返回即可。先让size总大小减一，定义一个指针指向头节点，遍历整个结点，找到指定位置的前一个元素，然后让该元素的指针的next为该元素next的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 swapPairs(ListNode head) {
ListNode pre= new ListNode(0);
pre.next=head;
ListNode temp=pre;
while(temp.next!=null&&temp.next.next!=null){
ListNode node1=temp.next;
ListNode node2=temp.next.next;
temp.next=node2;
node1.next=node2.next;
node2.next=node1;
temp=node1;
}
return pre.next;
}
}
解析：迭代法：定义一个前驱节点pre,它的next是head节点，用temp指针指向该节点，当temp的next和next的next都不为空时，即第一个和下一个节点都不为空，范围合理才可以交换。在此范围下，让temp的next为node2，让第一个节点的next为node2的next，再让node2的指向next指向node1上，让temp指向下一对的前驱节点上，不断循环完整个元素即可。
链表--删除链表的倒数第N个结点
题目：力扣题目链接
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
题解：
/**
* 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 removeNthFromEnd(ListNode head, int n) {
ListNode pre=new ListNode(0);
pre.next=head;
ListNode cur=pre;
ListNode cur1=pre;
int sum=0;
while(cur.next!=null){
cur=cur.next;
sum++;
}
if(sum-n<0){
return pre.next;
}
for(int i=1;i<sum-n+1;i++){
cur1=cur1.next;
}
cur1.next=cur1.next.next;
return pre.next;
}
}
题解：new一个head节点的前驱指针，让两个指针指向这个前驱节点，一个指针负责计算链表长度，另一个指针用for循环遍历到目标元素的前一个结点停止，然后cur1.next=cur1.next.next删除目标元素即可，最后返回head结点。
链表--链表相交
题目：力扣题目链接
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
示例 2：
题解：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A=headA;
ListNode B=headB;
int lenA=0,lenB=0;
while(A!=null){//求链表A的长度
lenA++;
A=A.next;
}
while(B!=null){//求链表B的长度
lenB++;
B=B.next;
}
A=headA;
B=headB;
while(lenA<lenB){//让A为最长链表的头
//1. 交换lenA, lenB
int t=lenA;
lenA=lenB;
lenB=t;
//2.交换A,B
ListNode tNode=A;
A=B;
B=tNode;
}
//求出长度差
int gap=lenA-lenB;
while(gap>0){
gap--;
A=A.next;
}
while(A!=null){
if(A==B){
return A;
}
A=A.next;
B=B.next;
}
return null;
}
}
解析： 
1.首先定义两个指针分别指向两个单链表的头节点，分别遍历两个单链表的长度得出lenA,lenB
2.让两个指针再次分别指向两个单链表的头节点，让A成为最长链表的头，所以需要交换lenA,lenB以及指针A，B
3.求出A，B的长度差，让A的指向不断右移，直到让链表B和链表A的尾部对其，如上图所示。
4.当A不为空，如果A和B相等，则A即为结果，否则A，B分别右移，不断遍历，得出结果。如果A等于空时，即两个链表没有交点，返回 null
链表--环形链表 II
题目：力扣题目链接
题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
题解：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast=head;
ListNode slow=head;
if(fast==null||fast.next==null){
return null;
}
while(fast.next!=null&&fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
if(slow==fast){//有环
ListNode index1=fast;
ListNode index2=head;
while(index1!=index2){
index1=index1.next;
index2=index2.next;
}
return index1;
}
}
return null;
}
}
解析：
-
判断链表是否有环
定义两个指针，快指针和慢指针，快指针走两步，慢指针走一步，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
-
寻找环的入口
在发现有环，即slow==fast时，定义两个指针，一个指向head，一个指向相遇点，让他们分别前进，如果这两个指针的下标相等时，此时的index即为环的入口地址
![[Python学习笔记]制作自动将xls文件转化为xlsx文件的程序](https://img2023.cnblogs.com/blog/2963444/202312/2963444-20231215101624969-1724676902.png)
