姚永坤的小窝

题目点击前往 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。 图示两个链表在节点 c1 开始相交： 题目数据 保证 整个链式结构中不存在环。 注意，函数返回结果后，链表必须保持其原始结构 。 解题思路 简单来说，就是求两个链表交点节点的指针。 这里同学们要注意，交点不是数值相等，而是指针相等。 我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置。 此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。 否则循环退出返回空指针。 1234567891011121314151617181920212223242526272829303132333435363738/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * th ...

题目点击前往 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。 示例1： 123输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。 示例2： 123输入：head = [1,2], pos = 0输出：返回索引为 0 的链表节点解释：链表中有一个环，其尾部连接到第一个节点。 示例3： 123输入：head = [1], pos = -1输出：返回 null解释：链表中没有环。 解题思路分两步走： 判断是否有环； 找环的入口。 判断是否有环 依然采用快慢指针的方法。 可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结 ...

题目点击前往 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 示例1： 12输入：head = [1], n = 1输出：[] 示例2： 12输入：head = [1], n = 1输出：[] 示例3： 12输入：head = [1,2], n = 1输出：[1] 解题思路 创建虚拟头节点，方便每次针对头结点的操作。 使用快慢指针来操作： 利用n来设置快指针和慢指针之间的间隔，当快指针指向null时删除当前节点的下一个节点并调整next指针。 123456789101112131415161718192021222324252627282930/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {Li ...

题目点击前往 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。 示例1： 12输入：head = [1,2,3,4]输出：[2,1,4,3] 示例2： 12输入：head = []输出：[] 示例3： 12输入：head = [1]输出：[1] 解题思路 创建虚拟头节点，方便每次针对头结点的操作。 1234567891011121314151617181920212223/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @return {ListNode} */var swa ...

题目点击前往 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 示例 1： 12输入：head = [1,2,3,4,5]输出：[5,4,3,2,1] 示例 2： 12输入：head = [1,2]输出：[2,1] 示例 3： 12输入：head = []输出：[] 解题思路双指针法 首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。 然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。 为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。 接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。 最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。 1234567891011121314151617181920212223242526/** * Definition for singly- ...

题目点击前往 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。 在链表类中实现这些功能： * get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。 * addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。 * addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。 * addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。 * deleteAtIndex(index)：如果索引 index 有效，则删 ...

题目点击前往 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 示例 1： 12输入：head = [1,2,6,3,4,5,6], val = 6输出：[1,2,3,4,5] 示例 2： 12输入：head = [], val = 1输出：[] 示例 3： 12输入：head = [7,7,7,7], val = 7输出：[] 解题思路 创建一个虚拟头节点来进行删除操作。 12345678910111213141516171819202122232425/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} ...

一、链表基础 链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。 链接的入口节点称为链表的头结点也就是head。 二、链表类型1、单链表 2、双链表 每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。 双链表既可以向前查询也可以向后查询。 3、循环链表 循环链表，顾名思义，就是链表首尾相连。可以用来解决约瑟夫环问题。 三、链表的存储方式 链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。 四、链表的操作1、删除节点 删除D节点，如图所示： 只要将C节点的next指针 指向E节点就可以了。 在C++里最好是再手动释放这个D节点，释放这块内存。 Java、Python 有自己的内存回收机制，就不用自己手动释放了。 2、添加节点 五、JS定义链表12345678class ListNode { val; next = null; constructor ...

一、什么是KMP说到KMP，先说一下KMP这个名字是怎么来的，为什么叫做KMP呢。 因为是由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母。所以叫做KMP。 二、KMP有什么用 KMP主要应用在字符串匹配上。 KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。 所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。 三、什么是前缀表 next数组就是一个前缀表（prefix table）。 前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。 前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。 四、最长相等前后缀 字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。 前缀表要求的就是相同前后缀的长度。 五、使用next数组来匹配 以下我 ...

题目点击前往 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1： 12输入：n = 3输出：[[1,2,3],[8,9,4],[7,6,5]] 示例 2： 12输入：n = 1输出：[[1]] 解题思路模拟过程 模拟顺时针画矩阵的过程: 填充上行从左到右 填充右列从上到下 填充下行从右到左 填充左列从下到上 由外向内一圈一圈这么画下去。 123456789101112131415161718192021222324252627282930313233343536/** * @param {number} n * @return {number[][]} */var generateMatrix = function(n) { let up=0, right=n-1, left= 0, bottom = n-1,； let k=1;//填写的数 let result = new Array(n).fill([]).map ...