环形链表的约瑟夫问题 思路： 1.先创建编号为1的人的节点作为循环链表的头结点 2.将剩下的所有的人创建对应的节点连接形成形成链表 3.将链表的首尾相连，因为对于约瑟夫问题，需要的是循环链表 4.进行游戏，每次让第m个人出圈 代码： import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @param m int整型 * @return int整...

对链表进行插入排序 思路： 1.只要还没有走到链表的倒数第二个节点，就表明插入排序还没有完成，就继续进行插入排序 2.对于每次插入排序，都需要遍历整个链表，只要是保持升序的就跳过，直到找到第一个打破升序的节点 3.先判断一下如果发现p.next为null，就表明原先已有的链表就是有序的，就可以直接返回头结点，就结束 4.否则就创建新的一个节点用于存这个节点的值 5.进行插排操作，对于插排操作分为两种情况：一种是插入链表的头结点前，这时候就将这个新的节点连在链表的头结点 不要忘记更新链表的头结点为该新的节点；第二种情况就是将节点插入两个节点的中间，就用一个while循环遍历找到第一个大于该节...

二叉树展开为单链表 思路： 1.先进行计数一下二叉树的节点的个数（递归） 2.开一个用于存树的节点的容器数组 3.将二叉树的节点存入数组容器中 4.再将二叉树的展开为单链表 代码： import java.util.*; import java.util.ArrayList; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val...

链表相加（一） 思路： 1.建立一个新的虚的头结点 2.只要两个链表中还有节点并且进位不为0，就需要进行相加操作 代码： import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { public ListNode ListAdd (ListNode l1, List...

链表的中间节点 思路： 1.设置两个指针，一个快指针fast和慢指针slow,快指针以两个节点两个节点进行移动，慢指针以一个节点进行移动 2.只要当fast指针和fast.next指针还没有指向null 3.最后slow指向的就是链表的中点 代码： import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ publ...

连续子链表的最大和 思路： 1.由于需要求最长的连续子串之和，所以先可以初始化为最小值 2.用动态规划的解决连续的最长的子串和的思想 3.用一个个max1记录两种选择中较大值：一种情况是将当前的数加到原先串的后面，另一种情况是将该数直接作为一个新的串的起始点 4.再与之前记录下来的最大的连续子串和与这次得到最长的子串和进行比较，得到最大值 代码： /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ c...

无环单链表插值 思路： 1.创建一个新链表的虚的头结点** 2.遍历数组，将每个数组中的值创建一个对应的节点 3.注意分为两种特殊的情况情况讨论：情况一：val的值是插在两个节点中间，val是插在链表的末尾 代码： import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution {...

链表错题 第六题： 1.如果是没有头结点的单向链表，当head=null,则是表示空链表 2.如果是有头结点的单向链表，当head->next=null，表示空链表 3.如果是没有头结点的循环链表，当head=null的时候，表示空链表 4.如果是有头结点的循环链表，当head->next=head的时候，表示空链表 第八题： 1.由于对于线性表的顺序存储，是可以通过已知首地址和存储的节点的占据的存储单元的大小，推出每个节点的位置，所以推出链表中的任意一个节点的地址的时间都是一样的，时间复杂度是O（1），所以是一种随机存储结构 2.随机存取和索引存取的区别就是，随机...

多选题 题1 4.关于链表，以下说法正确的是 （BC ） A需经常修改线性表Ｌ中的结点值适合采用链式结构 B需不断对线性表Ｌ进行删除插入适合采用链式结构 C带头结点的单链表，在表的第一个元素之前插入一个新元素与链表长度无关 D删除单链表中的最后一个元素，与链表长度无关 解析： A.如果需要经常修改线性表中的节点值，适合用顺序存储，因为顺序存储可以通过下标进行访问时间复杂度是O（1） D.删除链表的最后一个节点需要将链表的倒数第二个节点指向null，所以需要遍历链表找到倒数第二个节点，所以与链表的长度有关 而在链表的第一个元素前插入一个新的元素是与链表的长度无关的 题二： 5.便于...

划分链表 方法一：创建两个表之后进行连接 思路： 1.创建两个表的虚的头节点 2.遍历原先的表，将大于等于x的节点找出来连在存大的节点的表中，将小于x的节点找出来连在用于存小于x的节点的表中 3.再将两个表进行连接 代码： import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Soluti...

重排链表 方法一：暴力连接 思路： 1.观察排序后的序列我们可以发现，第一个节点后接最后一个节点，第二个节点后接倒数第二个节点，以此类推。故我们可以每次都找到最后一个节点并把它接在当前节点的后面 2.我们用一个指针p指向头节点，每次找到链表的最后一个节点并将它接在p所指节点的后面，然后p再指向下一个节点，直到p后面的节点数小于两个时停止 代码： import java.util.*; /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; ...

删除链表的节点 思路： 1.由于要进行删除操作，由于头结点是特殊的，所以为了同一操作，可以设置一个虚的头节点，连接到原链表的头结点 2.设置两个指针：一个指针pre（指向需要删除的节点的前一个节点），和一个指针cur（指向需要删除的节点） 代码： import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public ...

从尾到头打印链表 方法一：递归 思路： 我们都知道链表无法逆序访问，那肯定无法直接遍历链表得到从尾到头的逆序结果。但是我们都知道递归是到达底层后才会往上回溯，因此我们可以考虑递归遍历链表，因此三段式如下： 终止条件： 递归进入链表尾，即节点为空节点时结束递归。 返回值： 每次返回子问题之后的全部输出。 本级任务： 每级子任务递归地进入下一级，等下一级的子问题输出数组返回时，将自己的节点值添加在数组末尾。 具体做法： step 1：从表头开始往后递归进入每一个节点。 step 2：遇到尾节点后开始返回，每次返回依次添加一个值进入输出数组。 step 3：直到递归返回表头。 代...

复杂链表的复制 方法一：哈希表（unordered_map）: 图解： 思路： 1.假如链表没有随机指针, 我们的拷贝方式很简单, 只要先创建一个哨兵节点, 然后遍历一下给定链表, 创建新节点, 并不断和上个节点连接 2.本题的难点就在于每个节点还有一个指向空或其它节点的指针, 一种比较直观的想法就是先把整条链表连起来, 然后再挨着改变指针, 3.因此我们可以用哈希表来存放指针的映射关系, 然后根据将随机指针指向原链表随机指针映射在新链表的位置 4.算法实现：首先创建一个哨兵节点, 遍历一次原链表, 先将除随机指针外的部分创建并连接, 同时用哈希表记录指针之间的映射, 最后遍历一...