常见算法题分类总结之链表

相信我们大多数每每谈起算法题总会觉得很费脑子，很难，或者很多学弟学妹学完数据结构以后并不知道如何把学到的东西用到算法中去，但随着互联网公司的要求不断提高，想进一个好一点的互联网公司的技术岗，算法题都是必考的，只是难度的高低，我自己平时学也时长会觉得很难，但是在题目被做出来那一刻的喜悦和成就感总能让我忘记这些过程的艰辛。我觉得算法应该也是一个持续坚持的过程，也许我们现在不能手撕红黑树，但我们可以通过不断的学习，这些算法题像是以前的数学题，都有着一定的套路，我们先把理论知识学扎实了，再去分门别类地针对性的解决这一类一类的问题，对我而言这反正会是一场持久战，其实在不知不觉间这是我第二遍系统的学这些了，其实这些学习的日子真的过得很快，也很充实，时常会感谢曾经咬牙坚持的自己，即使自己很菜，也没有放弃，相信每一个牛逼的人都会有一段苦逼的日子，当然，我这还远远不够，只是个开始。

以下是我根据系统的课程和力扣官方题解以及力扣上各种大佬提供的方法自己总结出的一些相对简单易懂的方法来解决算法题，希望能够给大家提供一定的思路，然后自己比较再去选择便于自己理解并且能够手动实现的方法，这段时间我会将第一遍学习时的主要理论和第二遍重点学习的题目发出来，希望大家可以共同交流，共同进步，相信算法讨论起来能更加容易理解，深刻掌握。

当然，刚开始我的排版可能不太行，我慢慢修改，让大家看得更舒服。

我们先来看看什么是链表

⼀、链表介绍
 动态数组有明显的缺点：可能会造成内存的浪费
 是否可以⽤多少申请多少内存：链表可以
 链表是⼀种链式存储的线性表，所有元素的内存地址不⼀定是连续的

 Node节点

链表中的每⼀个内存块被称为节点Node，Node节点由两部分构成：
 存储数据(可以是任何类型)
 还需记录链上下⼀个节点的地址，即后继指针next，⽤来存储下⼀个节点的Node对象

链表的优缺点
数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移， 所以时间复杂度是 O(n) 在链表中插入和删除一个数据是非常快速的，我们只需要考虑相邻结点的指针改 变，所以对应的时间复杂度是 O(1)。

 二、常用链表
最常见的链表结构，它们分别是：单链表、双向链表和循环链表。

1.单链表
1）每个节点只包含一个指针，即后继指针。
2）单链表有两个特殊的节点，即首节点和尾节点。用首节点地址表示整条链表，尾节点的后 继指针指向空地址null。
3）性能特点：插入和删除节点的时间复杂度为O（1），查找的时间复杂度为O(n)。

2.循环链表
1）除了尾节点的后继指针指向首节点的地址外均与单链表一致。 2）适用于存储有循环特点的数据，比如约瑟夫问题。

3.双向链表
1）节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个 节点地址（后继指针next）。
2）首节点的前驱指针prev和尾节点的后继指针均指向空地址。
3）性能特点： 和单链表相比，存储相同的数据，需要消耗更多的存储空间。 插入、删除操作比单链表效率更高O(1)级别。

以删除操作为例，删除操作分为2种情况：给定数据值删除对应节点和给定节点地址删除节 点。
第一种情况：单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时 间复杂度为O(n)。
第二种情况：要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历直到p>next = q，时间复杂度为O(n)，而双向链表可以直接找到前驱节点，时间复杂度为 O(1)。
对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次 查找的位置p，每一次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查 找，所以平均只需要查找一半的数据。

4.双向循环链表
 在双向循环链表中，可见的不只有头指针head，还有尾节点end。这是和单链表的 区别。
 双向循环链表的头指针head的前一个节点指向end，尾节点end的后一个节点指向 head。

class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }}//环形链表public class Num141 {public boolean hasCycle(ListNode head) {Set set = new HashSet();ListNode p = head;while(p != null) {if(!set.add(p)) {return true;}p = p.next;}return false;}//进阶 用O(1)内存 —— 快慢指针public boolean hasCycle2(ListNode head) {if(head == null) return false;ListNode pre = head, cur = head;//快指针为空，表示遍历完了，能从这个循环走出来，说明无环while(cur != null && cur.next != null ) {pre = pre.next;cur = cur.next.next;if(pre == cur) return true;}return false;}}//环形链表2public class Num142 {public ListNode detectCycle(ListNode head) {ListNode p = head;Set set = new HashSet();while(p != null) {if(!set.add(p)) {return p;}p = p.next;}return null;}//进阶 使用O(1)空间 —— 快慢指针public ListNode detectCycle2(ListNode head) {if(head == null) return null;ListNode pre = head, cur = head;while(cur != null && cur.next != null) {pre = pre.next;cur = cur.next.next;if(pre == cur) {//相遇了，找到入环点cur = head; //相对运动while(cur != pre) {cur = cur.next;pre = pre.next;}//走出循环即两指针相遇，肯定为环的入口return cur;}}//走的是非环形列表return null;}}//快乐数public class Num202 {public boolean isHappy(int n) {int pre = n;int cur = getNext(n);while(pre != cur && cur != 1) {pre = getNext(pre);cur = getNext(getNext(cur));}return cur == 1;}private int getNext(int n) {int res = 0;while(n != 0) {int d = n % 10;res += d * d;n /= 10;}return res;}}//反转链表public class Num206 {public ListNode reverseList(ListNode head) {//pre是反转后链表的头节点 cur是原链表的头节点ListNode pre = null, cur = head, next = null;while(cur != null) {next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}//递归方法public ListNode reverseList2(ListNode head) {if(head == null || head.next == null) {return head;}ListNode newNode = reverseList2(head.next);//后面指向前面head.next.next = head;//取消指向后面的线head.next = null;return newNode;}}//反转链表2public class Num92 {//核心思路： cur后面的节点插入到pre后面的节点public ListNode reverseBetween(ListNode head, int left, int right) {//有时候连头节点一起反转，所以需要一个虚拟头节点ListNode hair = new ListNode(-1, head);ListNode pre = hair, cur = head;//根据left确定pre和head的关系//将cur放到left位置上for(int i = 0; i < left - 1; i++) {cur = cur.next;pre = pre.next;}//使用头插法for(int i = 0; i < right - left; i++) {//用临时变量记录要删除的节点ListNode temp = cur.next;//删除操作（单向链表无法自我删除，必须知道该节点和前一个节点）cur.next = cur.next.next;//temp指向pre的下一个节点temp.next = pre.next;//pre再指向temppre.next = temp;}//因为hair永远连着头节点//不能直接返回头节点的原因：头节点可能也一起反转了return hair.next;}}//k个一组翻转链表（hard）public class Num25 {/** * 1.找到k个要翻转的节点 * 2.进行翻转 返回翻转后的头节点和尾节点 * 3.对下一轮k个节点进行操作 * 4.将每轮的k个节点连接 * 法一报空指针异常 */public ListNode reverseKGroup(ListNode head, int k) {ListNode hair = new ListNode(-1, head);ListNode pre = hair;ListNode tail = null;while(head != null) {tail = pre;for(int i = 0; i < k; i++) {tail = tail.next;if(tail == null) {//说明末尾节点已经不足k个了return hair.next;}}ListNode[] revers = reverse(head, tail);//头节点和尾节点归位head = revers[0];tail = revers[1];pre.next = head;//pre继续移动，走向下一个要翻转的链表头部（也就是正在翻转链表的尾部）pre = tail;//head指针也移动head = pre.next;}return hair.next;}public ListNode[] reverse(ListNode head, ListNode tail) {//pre指向tail的下一个节点 方便和后续节点连接ListNode pre = tail.next, cur = head, next = null;//进循环说明链表还没翻转完成while(pre != tail) {next = cur.next;cur.next = pre;//后移继续迭代pre = cur;cur = next;}return new ListNode[]{tail, head};}//递归解法public ListNode reverseKGroup2(ListNode head, int k) {if(head == null || head.next == null) {return head;}ListNode firstHead = head;ListNode firstTail = head;for(int i = 0; i < k - 1; i++) {//把firstTail移动到要翻转节点的尾部firstTail = firstTail.next;if(firstTail == null) {//为null说明下一段要翻转的链表长度不够k 直接返回原链表return firstHead;}}ListNode secondHead = firstTail.next;//把链表分段firstTail.next = null;reverse2(firstHead);//翻转之后头尾变了firstHead.next = reverseKGroup2(secondHead, k);return firstTail;}//递归来解决private ListNode reverse2(ListNode head) {if(head == null || head.next == null) {return head;}ListNode next = head.next;ListNode newHead = reverse2(next);next.next = head;head.next = null;return newHead;}}//旋转链表public class Num61 {/* 核心思路： * 当k小于链表长度时 * 链表先成环，然后找到倒数第k个节点和倒数第k+1个节点 断开 * 再返回倒数第k个节点 * 当k大于链表长度时 有重复操作 取余减少操作*/public ListNode rotateRight(ListNode head, int k) {if(head == null || head.next == null) return head;//初始化链表长度为1int len = 1;ListNode oldTail = head;while(oldTail.next != null) {oldTail = oldTail.next;//记录链表长度len++;}//成环oldTail.next = head;ListNode newTail = head;//当k大于链表长度时 取余来除掉多余步数for(int i = 0; i < len - k % len - 1;i++) {//newTail找的就是倒数k+1个节点newTail = newTail.next;}//新链表头部ListNode newHead = newTail.next;//将头尾断开newTail.next = null;return newHead;}}public class Num24 {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null) return head;ListNode hair = new ListNode(-1, head);ListNode pre = hair;while(pre.next != null && pre.next.next != null) {ListNode one = pre.next;ListNode two = pre.next.next;//翻转one.next = two.next;two.next = one;pre.next = two;//继续后移迭代，因为此时one是下一链表头节点的前驱节点pre = one;}return hair.next;}//private ListNode reverse(ListNode head) {//if(head == null || head.next == null) return head;//ListNode newNode = reverse(head.next);//head.next.next = head;//head.next = null;//return newNode;//}//递归解法public ListNode swapPairs2(ListNode head) {if(head == null || head.next == null) return head;ListNode newHead = head.next;head.next = swapPairs2(newHead.next);newHead.next = head;head = newHead.next;return newHead;}}//删除链表的倒数第N个节点public class Num19 {public ListNode removeNthFromEnd(ListNode head, int n) {//有这个就错了//if(head == null || head.next == null) return head;ListNode hair = new ListNode(-1, head);//p先走n步，然后q和p同时走，两者相差n步，q指的就是倒数n+1那个节点ListNode p = head, q = hair;for(int i = 0; i  0)p = p.next;}while(p != null) {p = p.next;q = q.next;}//删除节点q.next = q.next.next;//可以省略//q.next.next = null;return hair.next;}}//删除排序链表中的重复元素public class Num83 {public ListNode deleteDuplicates(ListNode head) {//没有也给过了//if(head == null) return null;ListNode cur = head;while(cur != null && cur.next != null) {if(cur.next.val == cur.val) {cur.next = cur.next.next;} else {cur = cur.next;}}return head;} }//删除排序链表中的重复元素2public class Num82 {//双指针public ListNode deleteDuplicates(ListNode head) {if(head == null) return null;ListNode hair = new ListNode(-1, head);ListNode pre = hair, cur = head;while(cur != null && cur.next != null) {if(cur.next.val != cur.val) {pre = pre.next;cur = cur.next;}else {//下一个是重复的值while(cur != null && cur.next != null &&cur.val == cur.next.val) {cur = cur.next;}pre.next = cur.next;cur = cur.next;}}return hair.next;}}

创作打卡挑战赛 赢取流量/现金/CSDN周边激励大奖