1、移除链表元素
题意：删除链表中等于给定值 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 fir=new ListNode();//添加头节点，统一所有节点的删除方式
ListNode fir1=fir;
//fir1用于指定头部节点，注意fir指针移动，但是fir1不会移动，赋值的是数据地址空间
fir.next=head;
while(fir.next!=null){
if(fir.next.val==val){
fir.next=fir.next.next;
//这里把前面数据的next指针指向下下个节点，fir不要动，因此fir.next还有可能等于val
}
else{
fir=fir.next;
}
}
return fir1.next;
}
}2、设计链表
在链表类中实现这些功能：
- 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;
public ListNode(){}
public ListNode(int val){this.val=val;}
public ListNode(int val,ListNode next){
this.val=val;
this.next=next;
}
}
class MyLinkedList {
ListNode head;//头结点
ListNode tail; //尾部节点，永远指向数据最后一个节点
int length=0;
public MyLinkedList() {
head=new ListNode();
}
//这个是自己想的方法 设定一个尾部指针，永远指向最后一个数据，那就需要维护好tail指针
// public int get(int index) {
// if(index>=length||index<0){ //index=0的情况
// return -1;
// }
// ListNode cur=head;
// for(int i=0;i<=index;i++){
// cur=cur.next;
// }
// return cur.val;
// }
// public void addAtHead(int val) {
// ListNode member=new ListNode(val);
// ListNode nn=head.next;
// head.next=member;
// member.next=nn;
// length++;
// if(length==1){ //这里记得添加头部如果长度为1说明只有一个数据，那么tail需要指向最后一个数据
// tail=member;
// }
// }
// public void addAtTail(int val) {
// ListNode tt=new ListNode(val);
// if(tail!=null) //这一步很重要，尾部不为空，那尾部后面才能直接添加数据，否则就是直接把tail赋值
// tail.next=tt;
// tail=tt;
// length++;
// if(length==1){ //如果长度为1，那么head头部节点需要指向新数据
// head.next=tt;
// }
// //这一步判断length=1和上一步判断length=1的步骤很重要，才能把head和tail链接起来
// }
// public void addAtIndex(int index, int val) {
// if(index==length){
// addAtTail(val);
// }
// else if(index<=0){
// addAtHead(val);
// }
// else if(index>0&&index<length){
// //添加数据在第index个前面的数据，所以只需要找到index的前一个节点
// ListNode nn=new ListNode(val);
// ListNode cur=head;
// for(int i=0;i<index;i++){
// cur=cur.next;
// }
// nn.next=cur.next;
// cur.next=nn;
// length++;
// }
// }
// public void deleteAtIndex(int index) {
// if(index>=0&&index<length){
// ListNode pre=head;
// for(int i=0;i<index;i++){
// pre=pre.next;
// }
// pre.next=pre.next.next;
// if(index==length-1){//删除需要注意tail节点，如果删除最后一个节点，那tail需要往前移动
// tail=pre;
// }
// length--;
// }
// }
//获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
public int get(int index) {
//如果index非法，返回-1
if (index < 0 || index >= length) {
return -1;
}
ListNode currentNode = head;
//包含一个虚拟头节点，所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) {
currentNode = currentNode.next;
}
return currentNode.val;
}
//在链表最前面插入一个节点，等价于在第0个元素前添加
public void addAtHead(int val) {
addAtIndex(0, val);
}
//在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
public void addAtTail(int val) {
addAtIndex(length, val);
}
public void addAtIndex(int index, int val) {
if (index > length) {
return;
}
if (index < 0) {
index = 0;
}
length++;
//找到要插入节点的前驱
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
ListNode toAdd = new ListNode(val);
toAdd.next = pred.next;
pred.next = toAdd;
}
//删除第index个节点
public void deleteAtIndex(int index) {
if (index < 0 || index >= length) {
return;
}
length--;
if (index == 0) {
head = head.next;
return;
}
ListNode pred = head;
for (int i = 0; i < index ; i++) {
pred = pred.next;
}
pred.next = pred.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);
*/3、反转链表
题意：反转一个单链表。
示例: 输入: 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 {
//1、普遍遍历方法
// public ListNode reverseList(ListNode head) {
// //思路1：设定一个数组存储所有元素，再反向搜索链接
// //思路2：设定一个指针，每次遍历都从头部插入
// ListNode pre=head;
// ListNode cur=head;
// ListNode newHead=null;
// while(cur!=null){
// cur=cur.next;//先保存当前节点的下一个链表
// pre.next=newHead;//当前节点就插入到了头部前面
// newHead=pre;//移动头部节点
// pre=cur;//pre继续移动到下一个链表节点
// }
// return newHead;
// }
//2、递归方法
//这个关键是明白递归方法的2个参数代表的意思，一个是代表新头部，一个是待遍历的链表
public ListNode reverse(ListNode newHead,ListNode cur){
if(cur==null){return newHead;}//递归结束 返回新得头部
ListNode temp=cur.next;//先保存当前节点的下一个链表
cur.next=newHead;//当前节点就插入到了头部前面
return reverse(cur,temp); //递归，新得头部是cur 下一个链表节点是temp
}
public ListNode reverseList(ListNode head) {
return reverse(null,head);
}
}4、两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
/**
* 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 cur=head;
ListNode pre=null; //初始的pre是空的
while(cur!=null){
ListNode temp=cur.next;//保存中间的节点
if(temp!=null){
cur.next=cur.next.next;//相当于直接删除中间的节点
temp.next=cur;//再把中间节点插入pre和cur之间
if(pre!=null)//一开始pre为空就代表不需要pre
pre.next=temp;//这一步需要把之前节点的next指向temp
else{
head=temp;//这一步需要改变一下head节点
}
}
//循环下一个 此时1，2，3，4就是 2 1 3 4 cur为1，cur下一个就是3
pre=cur;
cur=cur.next;
}
return head;
}
}5、删除链表的倒数第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) {
//设置双指针，慢指针停留第一个，快指针迅速遍历n个节点，
// 如果第n个节点后面不为空，那慢指针才移动
//也就是快慢指针的滑动窗口永远是n个数据
// ListNode slow=head;
// ListNode fast=head;
// ListNode pre=null;
// while(n>1){
// n--;
// fast=fast.next;
// }
// while(fast.next!=null){
// pre=slow;
// slow=slow.next;
// fast=fast.next;
// }
// if(pre!=null)
// pre.next=pre.next.next;
// else{//为空代表就是删除第一个数据
// return head.next;
// }
// return head;
//可以改进的点：设置虚拟头结点，slow指向待删除数据的上一个节点
ListNode fir=new ListNode();
fir.next=head;
ListNode slow=fir;
ListNode fast=fir;
while(n-->-1){
fast=fast.next;
}
while(fast!=null){
slow=slow.next;
fast=fast.next;
}
slow.next=slow.next.next;
return fir.next;
}
}6、链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构
/**
* 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) {
//方法1：推理证明，假设节点为倒数第c个，A+B-C=B+A-C 互相遍历对方一定会在交点相等
//A+B-C代表先遍历完A再遍历B-C个对方的节点就到了交点，同理B+A-C
ListNode p=headA;
ListNode q=headB;
while(p!=q){
// if(p==null){
// p=headB;
// }
// else{
// p=p.next;
// }
// if(q==null){
// q=headA;
// }
// else{
// q=q.next;
// }
p=p==null?headB:p.next;
q=q==null?headA:q.next;
}
return p;
//方法2：先确定2个链表的长度，然后尾部对齐，如果相交肯定是最尾部
}
}7、环形链表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) {
//方法1：用哈希表存储节点，然后遇到重复节点会判断
//但是题目要求O(1)内存
//方法2：根据复杂的推理证明，
// 假设从头结点到环形入口节点 的节点数为x。
// 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。
// 从相遇节点 再到环形入口节点节点数为 z
// fast指针走过的节点数 = slow指针走过的节点数 * 2：(x + y) * 2 = x + y + n (y + z)
// 推出 x = (n - 1) (y + z) + z 这个公式推导出来的
// 公式理解：x的长度就是头结点一步一步走到入口节点处，而另外一个指针从相遇节点处出发，
// 经过（n-1)个环的长度为（y+z)再走Z个节点也就到了入口节点和头结点相遇，这才是长度相等
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(slow==fast) {
//这一步先找到相遇节点
slow=head;
while(slow!=fast){//一个节点从头出发，一个从相遇节点出发，一定会相遇
slow=slow.next;
fast=fast.next;
}
return slow;
}
}
return null;
}
}
