算法：链表（力扣+牛客经典题）
链表
力扣
203. 移除链表元素
思路：使用while循环每找到指定的值，就把下一个节点指向下下个节点的位置
/**
* 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) {
// 初始化链表 第一个值为0
ListNode listNode = new ListNode(0,head);
// 因为单链表是不可逆的，所以把listNode的 地址赋给 temp，就可以控制temp来操作链表，
ListNode temp = listNode;
// 循环找值，并去掉
while (temp.next != null){
if (temp.next.val == val){
// 如果temp.next有值，最不济temp.next.next为null，而把null重新赋给temp.next也不会报空节点异常
temp.next = temp.next.next;
} else {
temp = temp.next;
}
}
// 因为listNode的初始值为0，他的下一个才是原数组head（删掉了指定的值）
return listNode.next;
}
}
206. 反转链表
思路：就是先设一个值为null，再用head开头的值指向这个null，再把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 reverseList(ListNode head) {
ListNode a = null;
ListNode listNode = head;
// 循环这个链表
while (listNode!=null){
// 设置一个b指向listNode 的下一个节点
ListNode b = listNode.next;
// listNode最前面的值的后一个指向a这个链表
listNode.next = a;
// 再把listNode这个链表赋给a
a = listNode;
// listNode 指向他的下一个节点，用于循环
listNode = b;
}
return a;
}
}
24. 两两交换链表中的节点
思路：每次找到要旋转的个数，并旋转，剩余的链表进入递归，并挨个拼接
/**
* 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 listNode = reverseKGroup(head, 2);
return listNode;
}
public ListNode reverseKGroup (ListNode head, int k) {
//找到每次翻转的尾部
ListNode tail = head;
//遍历k次到尾部
for(int i = 0; i < k; i++){
//如果不足k到了链表尾，直接返回，不翻转
if(tail == null) {
return head;
}
tail = tail.next;
}
// 这里就是翻转链表的知识点
//翻转时需要的前序和当前节点
ListNode pre = null;
ListNode cur = head;
//在到达当前段尾节点前
while(cur != tail){
//翻转
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
//当前尾指向下一段要翻转的链表
head.next = reverseKGroup(tail, k);
return pre;
}
}
19. 删除链表的倒数第 N 个结点
思路：使用双指针，先让前节点走N+1步，后节点不动，然后遍历前节点，直到前节点指向null的时候，后节点的节点指向倒数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 x = new ListNode(0,head);
ListNode a = x;
// 这一步和下面的for循环就是指，b链表要先走n+1步
ListNode b = x.next;
for (int i = 0; i < n; i++) {
b = b.next;
}
// 通过b走到头了之后，a链表指向的就是倒数n+1个节点
while (b!=null){
a = a.next;
b = b.next;
}
// a下一个节点直线a的下下个节点就可以了
a.next = a.next.next;
return x.next ;
}
}
160.链表相交
思路：意思就是说两个链表后面节点可能相同，那么后面的长度也是一样的，就需要把前面长的链表给截成和短的链表一样长，然后进行比较，不一样就一起后移
/**
* 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) {
// 使用AL和BL记录两个链表的长度
int AL = 0;
int BL = 0;
ListNode aL = headA;
ListNode bL =headB;
while (aL!=null){
AL++;
aL = aL.next;
}
while (bL!=null){
BL++;
bL = bL.next;
}
aL = headA;
bL = headB;
// 截取长的链表，使两个链表一样长
if (AL > BL){
for (int i = 0; i < AL - BL; i++) {
aL = aL.next;
}
}else {
for (int i = 0; i < BL - AL; i++) {
bL = bL.next;
}
}
// 循环比较是否相同，返回相同的部分
while (aL!=null){
if (aL == bL){
return aL;
}
aL = aL.next;
bL = bL.next;
}
return null;
}
}
142.环形链表 II
思路：一、先要判断是否是循环链表；二、要找出循环入口节点
一判断是否循环
使用快慢指针，前指针每次走两个节点，后指针每次走一个节点，如果是循环链表的话，前一个指针会追上后一个指针的，可以做一下试验：
如示例一：前走两步，后走一步
两个从三开始
第一次：前：2,0；后：2；
第二次：前：-4,2；后：0；
第三次：前：0,-4；后：-4；
结束
二、要找出循环入口节点
先定位到判断循环链表的那个节点，如上诉的0这个节点，再从开头（3）走一个值，他们两个每次只走一步，如果他们相等的话，就是那个节点循环的头
/**
* 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 left = head;
ListNode right = head;
// 因为right要走两步，怕出现空指针异常（如果 right.next 为null的话，right.next.next就会空指针异常）
while (right != null && right.next != null){
// 判断是否循环
left = left.next;
right = right.next.next;
if (left == right){
left = head;
// 找循环的头节点
while (left != right){
left = left.next;
right = right.next;
}
return left;
}
}
return null;
}
}
牛客：
BM1 反转链表（同力扣：206.循环链表，上面有讲）
BM2 链表内指定区间反转
思路：截取翻转，并连接
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
public ListNode reverseBetween (ListNode head, int m, int n) {
//设置虚拟头节点
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode pre = dummyNode;
//1.走left-1步到left的前一个节点
for(int i=0;i<m-1;i++){
pre = pre.next;
}
//2.走roght-left+1步到right节点
ListNode rigthNode = dummyNode;
for(int i=0;i<n;i++){
rigthNode = rigthNode.next;
}
//3.截取出一个子链表
ListNode leftNode = pre.next;
ListNode cur = rigthNode.next;
//4.切断链接
pre.next=null;
rigthNode.next=null;
//5.反转局部链表
reverseLinkedList(leftNode);
//6.接回原来的链表
pre.next = rigthNode;
leftNode.next = cur;
return dummyNode.next;
}
//反转局部链表
private void reverseLinkedList(ListNode head){
ListNode pre = null;
ListNode cur = head;
while(cur!=null){
//Cur_next 指向cur节点的下一个节点
ListNode Cur_next = cur.next;
cur.next = pre;
pre = cur;
cur = Cur_next ;
}
}
}
BM3 链表中的节点每k个一组翻转（同力扣：24. 两两交换链表中的节点，上面有讲）
BM4 合并两个排序的链表
思路：一直循环，比较两个链表当时的大小，小的那个加入新的链表，并指向后一个节点，大的链表不动，最后哪个链表还有剩的话，就自动加入后面就可以了
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode listNode = new ListNode(-1);
// 新的链表
ListNode x = listNode;
while (list1 != null&&list2!=null){
// 判断哪个链表的节点大，把小的节点接入新的链表
if (list1.val > list2.val){
x.next = list2;
x = x.next;
list2 = list2.next;
}else {
x.next = list1;
x = x.next;
list1 = list1.next;
}
}
//哪个链表还有剩，直接连在后面
if(list1 != null)
x.next = list1;
else
x.next = list2;
return listNode.next;
}
}
BM5 合并k个已排序的链表
思路：这里使用了PriorityQueue优先队列（最小堆），这个数据结构可以把最小值顶到堆的最前面，使用我只需要，把list里面的所有值放入最小堆里面，然后遍历最小堆，得到一个完整的新链表就可以了
import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
// 优先队列（最小堆）
Queue<Integer> queue = new PriorityQueue<>();
// 加入最小堆里面
lists.forEach(x->{
while (x!=null){
queue.offer(x.val);
x = x.next;
}
});
// 新建一个链表用来装遍历最小堆的最前面就可以了
ListNode listNode = new ListNode(-1);
ListNode x = listNode;
while (!queue.isEmpty()){
x.next = new ListNode(queue.poll());
x = x.next;
}
return listNode.next;
}
}
BM6 判断链表中是否有环（同力扣：142.环形链表 II的第一个观点寻找循环链表，上面有讲）
BM7 链表中环的入口结点（同力扣：142.环形链表 II的第二个观点寻找循环链表入口节点，上面有讲）
BM8 链表中倒数最后k个结点
思路：双指针，先让前节点走N+1步，后节点不动，然后遍历前节点，直到前节点指向null的时候，后节点的节点指向倒数N个节点的前一个节点
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode FindKthToTail (ListNode pHead, int k) {
if (pHead==null){
return pHead;
}
ListNode x = pHead;
for (int i = 0; i < k; i++) {
if (x == null){
return null;
}
x = x.next;
}
ListNode y = pHead;
while (x != null){
x = x.next;
y = y.next;
}
return y;
}
}
BM9 删除链表的倒数第n个节点（同力扣：19. 删除链表的倒数第 N 个结点，上面有讲）
BM10 两个链表的第一个公共结点（同力扣：160.链表相交，上面有讲）
BM11 链表相加(二)
思路：先翻转两个链表（因为加法都是从个位加着走，所以翻转一个从头一个加到尾，再翻转一下，就是我们需要的值），就是取到每个节点值相加，如果进位就往前加一个，如果到最后一个节点还需要进位，就再下一个节点输入一。
import java.util.*;
import java.math.BigInteger;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
public ListNode addInList (ListNode head1, ListNode head2) {
// 翻转
ListNode a = reverse(head1);
ListNode b = reverse(head2);
// c是判断需要进位不，如果是0就是没进位，1就是需要进位的那个加上1
int c = 0;
// x是a链表节点的值
int x = 0;
// y是b链表节点的值
int y = 0;
// 通过d来记录listNode的地址，listNode变动的时候，d还是指向没变动的头结点
ListNode listNode = new ListNode(-1);
ListNode d = listNode;
while (a!=null||b!=null){
// 给x赋值
if (a!=null){
x = a.val;
a = a.next;
}else {
x = 0;
}
// 给y赋值
if (b!=null){
y = b.val;
b = b.next;
}else {
y = 0;
}
// 让listNode.next指向新建一个链表
// (x+y+c)%10 可以得到个位的值，存入新的链表
listNode.next = new ListNode((x+y+c)%10);
listNode = listNode.next;
// 判断是否进位 如果十位有值 c就位十位的值
c = (x + y + c)/10;
}
// 最后当两条链表都加完的时候，进位不为0的时候，则需要再加上这个进位
if(c > 0){
listNode.next = new ListNode(c);
}
// 再次翻转
return reverse(d.next);
}
// 反转链表
ListNode reverse(ListNode head){
if(head == null) {
return head;
}
ListNode cur = head;
ListNode node = null;
while(cur != null){
ListNode tail = cur.next;
cur.next = node;
node = cur;
cur = tail;
}
return node;
}
}
BM12 单链表的排序
思路：一、变成数组然后排序重新写入链表；二、使用PriorityQueue优先队列（最小堆）排序取值就可以了
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类 the head node
* @return ListNode类
*/
public ListNode sortInList (ListNode head) {
// 最小堆
PriorityQueue<Integer> queue = new PriorityQueue<>();
// 存入最小堆
while (head!=null){
queue.add(head.val);
head = head.next;
}
ListNode listNode = new ListNode(-1);
ListNode x = listNode;
// 从最小堆取值，然后组成新的数组
while (!queue.isEmpty()){
listNode.next = new ListNode(queue.poll());
listNode = listNode.next;
}
return x.next;
}
}
BM13 判断一个链表是否为回文结构
思路：把链表的值写入一个数组里面，然后利用双指针判断是否是回文就可以了（就是第一个指针指向头，后一个指针指向尾，判断是否相等，相等就向前比较就可以了）
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类 the head
* @return bool布尔型
*/
public boolean isPail (ListNode head) {
ArrayList<Integer> list = new ArrayList<>();
// 变成一个list集合
while (head!=null){
list.add(head.val);
head = head.next;
}
int x = 0;
int y = list.size() - 1;
// 双指针判断是否为回文
while (x<y){
if (!list.get(x++).equals(list.get(y--))){
return false;
}
}
return true;
}
}
BM14 链表的奇偶重排
思路：看代码
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
public ListNode oddEvenList (ListNode head) {
//如果链表为空，不用重排
if(head == null)
return head;
//even开头指向第二个节点，可能为空
ListNode even = head.next;
//odd开头指向第一个节点
ListNode odd = head;
//指向even开头
ListNode evenhead = even;
while(even != null && even.next != null){
//odd连接even的后一个，即奇数位
odd.next = even.next;
//odd进入后一个奇数位
odd = odd.next;
//even连接后一个奇数的后一位，即偶数位
even.next = odd.next;
//even进入后一个偶数位
even = even.next;
}
//even整体接在odd后面
odd.next = evenhead;
return head;
}
}
BM15 删除有序链表中重复的元素-I
思路：因为是有序的，所以只要后一个节点的值与自己节点一样，把后一个节点指向下下个节点就可以了
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode deleteDuplicates (ListNode head) {
// write code here
ListNode a = head;
while (head!=null && head.next!=null){
// 如果后一个节点和自己节点值相等的话，就删除掉，并不需要移动自己的指针
if (head.val == head.next.val){
head.next = head.next.next;
continue;
}
head = head.next;
}
return a;
}
}
BM16 删除有序链表中重复的元素-II
思路：添加一个表头，然后看下一个节点与下下个节点是否相同，如果相同，再循环看看后面的节点的值是否一样，相同就全部跳过
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode deleteDuplicates (ListNode head) {
//空链表
if(head == null)
return null;
ListNode res = new ListNode(0);
//在链表前加一个表头
res.next = head;
ListNode cur = res;
while(cur.next != null && cur.next.next != null){
//遇到相邻两个节点值相同
if(cur.next.val == cur.next.next.val){
int temp = cur.next.val;
//将所有相同的都跳过
while (cur.next != null && cur.next.val == temp)
cur.next = cur.next.next;
}
else
cur = cur.next;
}
//返回时去掉表头
return res.next;
}
}