网站 中文版与英文版的后台有什么不同,wordpress主题压缩包安装提示无效,制作wordpress页面模板下载地址,哪些网站做的最好链表
1.24. 两两交换链表中的节点
力扣题目链接(opens new window)
给定一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后的链表。
你不能只是单纯的改变节点内部的值#xff0c;而是需要实际的进行节点交换。 思路
使用虚拟头结点会很方便#xff…链表
1.24. 两两交换链表中的节点
力扣题目链接(opens new window)
给定一个链表两两交换其中相邻的节点并返回交换后的链表。
你不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。 思路
使用虚拟头结点会很方便要不每次针对头结点没有前一个指针指向头结点还要单独处理。
链表听说用虚拟头节点会方便很多 (opens new window)。
接下来就是交换相邻两个元素
初始时cur指向虚拟头结点然后进行如下三步 操作之后链表如下 看这个可能就更直观一些了 public class Swap_Nodes_in_Pairs {public static class ListNode {//ListNode 是一个静态内部类用于表示链表中的节点。int val;//存储节点的值。ListNode next;//指向下一个节点的引用。public ListNode(int val) {//构造函数用于创建一个新的节点并将其值初始化为传入的参数 val。this.val val;}}public ListNode swapPairs3(ListNode head) {ListNode dummy new ListNode(0);//创建一个值为 0 的虚拟头节点 dummy。虚拟头节点的引入能够统一处理链表头节点的交换情况避免了对头节点进行特殊处理的复杂性。dummy.next head;//把虚拟头节点的 next 指针指向原链表的头节点 head从而将虚拟头节点接入到原链表中。ListNode cur dummy;//创建一个指针 cur 并初始化为虚拟头节点后续会使用这个指针来遍历链表。while (cur.next ! null cur.next.next ! null) {//保证了当前 cur 节点后面至少存在两个节点这样才能进行节点的两两交换。ListNode node1 cur.next; //要交换的两个节点中的第一个节点。ListNode node2 cur.next.next;//要交换的两个节点中的第二个节点。cur.next node2;//实现了当前节点跳过 node1 直接指向 node2。node1.next node2.next;//第 1 个节点指向第 2 个节点的下一个节点node2.next node1; //把 node2 的 next 指针指向 node1完成了 node1 和 node2 两个节点的交换。cur cur.next.next;//将 cur 指针移动到当前交换完成的节点对的下一个节点对的前一个节点位置为下一轮的节点交换做准备。}return dummy.next;//当循环结束后链表中所有相邻的节点对都已经完成了交换操作。由于虚拟头节点的 next 指针指向的就是交换后的链表头节点所以直接返回 dummy.next。}
}
时间复杂度
我们遍历链表一次每次处理两个节点。由于每个节点只被访问一次因此时间复杂度为 O(n)其中 n 是链表中节点的数量。 空间复杂度
该方法只使用了常量级别的额外空间来存储指针如 dummy , cur , node1 , node2 并没有使用任何额外的数据结构来存储节点。因此空间复杂度为 O(1)。
时间复杂度O(n)
空间复杂度O(1)
链表 1 - 2 - 3 - 4
1. 初始化
创建一个虚拟头节点 dummy其值为 0。将 dummy 的 next 指针指向原链表的头节点 head这里 head 指向节点 1。初始化指针 cur 指向虚拟头节点 dummy。
此时链表结构如下dummy 为虚拟头节点
dummy(0) - 1 - 2 - 3 - 4^cur
2. 第一次交换处理节点 1 和 2
获取要交换的节点 ListNode node1 cur.next;node1 指向节点 1。ListNode node2 cur.next.next;node2 指向节点 2。 交换节点 cur.next node2;让 cur即 dummy的 next 指针指向 node2节点 2。node1.next node2.next;让 node1节点 1的 next 指针指向 node2 的下一个节点节点 3。node2.next node1;让 node2节点 2的 next 指针指向 node1节点 1。
交换后链表结构变为
dummy(0) - 2 - 1 - 3 - 4^cur移动指针cur cur.next.next;将 cur 指针移动到当前交换完成的节点对2 - 1的下一个节点对的前一个节点节点 1。
3. 第二次交换处理节点 3 和 4
此时 cur 指向节点 1继续循环
获取要交换的节点 ListNode node1 cur.next;node1 指向节点 3。ListNode node2 cur.next.next;node2 指向节点 4。 交换节点 cur.next node2;让 cur节点 1的 next 指针指向 node2节点 4。node1.next node2.next;让 node1节点 3的 next 指针指向 node2 的下一个节点这里为 null。node2.next node1;让 node2节点 4的 next 指针指向 node1节点 3。
交换后链表结构变为
dummy(0) - 2 - 1 - 4 - 3 - null^cur移动指针cur cur.next.next;将 cur 指针移动到当前交换完成的节点对4 - 3的下一个节点对的前一个节点但此时 cur.next null不满足循环条件循环结束。
4. 返回结果
由于 dummy.next 指向节点 2所以最终返回交换后的链表 2 - 1 - 4 - 3。
2.234.回文链表
力扣题目链接(opens new window)
请判断一个链表是否为回文链表。
示例 1:
输入: 1-2输出: false
示例 2:
输入: 1-2-2-1输出: true
思路
数组模拟
最直接的想法就是把链表装成数组然后再判断是否回文。
反转后半部分链表
分为如下几步
用快慢指针快指针有两步慢指针走一步快指针遇到终止位置时慢指针就在链表中间位置同时用pre记录慢指针指向节点的前一个节点用来分割链表将链表分为前后均等两部分如果链表长度是奇数那么后半部分多一个节点将后半部分反转 得cur2前半部分为cur1按照cur1的长度一次比较cur1和cur2的节点数值
如图所示 public class Palindrome_Linked_List {public static class ListNode {//ListNode 是一个静态内部类用于表示链表中的节点。int val;//存储节点的值。ListNode next;//指向下一个节点的引用。public ListNode(int i) {this.val i;}}public boolean isPalindrome1(ListNode head) {int len 0;//初始化一个整型变量 len 用于记录链表的长度初始值为 0。ListNode cur head;//创建一个指针 cur 并将其指向链表的头节点 head用于遍历链表。while (cur ! null) {//while 循环遍历链表只要 cur 不为 null就表示还没有遍历到链表的末尾。len;//每遍历一个节点就将 len 的值加 1。cur cur.next;//将 cur 指针移动到下一个节点。}cur head;//将 cur 指针重新指向链表的头节点为将链表元素存储到数组做准备。int[] res new int[len];//创建一个长度为 len 的整型数组 res用于存储链表中的元素。for (int i 0; i res.length; i){//for 循环遍历数组将链表中的元素依次存储到数组中。res[i] cur.val;//将当前 cur 指针所指向节点的值存储到数组的第 i 个位置。cur cur.next;//将 cur 指针移动到下一个节点。}for (int i 0, j len - 1; i j; i, j--){//使用双指针法i 从数组的起始位置开始j 从数组的末尾位置开始向中间移动。只要 i j就表示还没有比较完所有对称位置的元素。if (res[i] ! res[j]){//如果数组中对称位置的元素不相等说明链表不是回文链表直接返回 false。return false;}}return true;//如果循环结束后都没有发现不相等的元素说明链表是回文链表返回 true。}
} 时间复杂度
1. 计算链表长度我们遍历链表一次以计算长度时间复杂度为 O(n)其中 \(n\) 是链表的节点数。
2. 存储链表元素到数组我们再次遍历链表将元素存储到数组中时间复杂度也是 O(n)。
3. 比较数组元素最后我们进行一次比较时间复杂度为 O(n/2)因为只需比较一半的元素但在大O表示法中常数因子通常被省略因此这部分的时间复杂度也是 O(n)。 综合以上步骤总的时间复杂度为 O(n)。
空间复杂度
1. 数组存储我们创建了一个长度为 n 的整型数组来存储链表的元素因此空间复杂度为 O(n)。 2. 其他变量除了数组外使用的其他变量如指针和整型变量占用的空间是常数级别的O(1)。 因此总的空间复杂度为 O(n)。
时间复杂度: O(n)
空间复杂度: O(n)
1 - 2 - 2 - 1
1. 初始化变量
len 初始化为 0用于记录链表的长度。cur 指针初始化为指向链表的头节点 head这里 head 指向值为 1 的节点。
此时链表结构如下
1 - 2 - 2 - 1
^
cur2. 统计链表长度
第一次循环cur 指向值为 1 的节点len 加 1 变为 1cur 移动到下一个节点值为 2 的节点。第二次循环cur 指向值为 2 的节点len 加 1 变为 2cur 移动到下一个节点另一个值为 2 的节点。第三次循环cur 指向值为 2 的节点len 加 1 变为 3cur 移动到下一个节点值为 1 的节点。第四次循环cur 指向值为 1 的节点len 加 1 变为 4cur 移动到 null循环结束。
此时得到链表长度 len 4。
3. 将链表元素存储到数组中
cur 重新指向链表的头节点值为 1 的节点。创建长度为 4 的整型数组 res。第一次循环i 0res[0] 赋值为 cur 指向节点的值 1cur 移动到下一个节点值为 2 的节点。第二次循环i 1res[1] 赋值为 cur 指向节点的值 2cur 移动到下一个节点另一个值为 2 的节点。第三次循环i 2res[2] 赋值为 cur 指向节点的值 2cur 移动到下一个节点值为 1 的节点。第四次循环i 3res[3] 赋值为 cur 指向节点的值 1cur 移动到 null循环结束。
此时数组 res 中的元素为 [1, 2, 2, 1]。
4. 使用双指针法比较数组对称位置的元素
第一次比较i 0j 3res[0] 1res[3] 1两者相等继续循环。第二次比较i 1j 2res[1] 2res[2] 2两者相等继续循环。此时 i 2j 1不满足 i j 的条件循环结束。
5. 返回结果
由于在比较过程中没有发现不相等的元素所以判断该链表是回文链表返回 true。
3.143.重排链表
力扣题目链接(opens new window) 数组模拟
把链表放进数组中然后通过双指针法一前一后来遍历数组构造链表。
双向队列模拟
把链表放进双向队列然后通过双向队列一前一后弹出数据来构造新的链表。
直接分割链表
将链表分割成两个链表然后把第二个链表反转之后在通过两个链表拼接成新的链表。
如图 public class Reorder_List {public static class ListNode {//ListNode 是一个静态内部类用于表示链表中的节点。int val;//存储节点的值。ListNode next;//指向下一个节点的引用。public ListNode(int i) {this.val i;}}public void reorderList2(ListNode head) {DequeListNode de new LinkedList();//双端队列允许在队列的两端进行插入和删除操作ListNode cur head.next;//指针 cur 并将其指向链表头节点的下一个节点因为头节点 L0 不需要存入队列后续会作为重排后链表的起始节点。while (cur ! null){//while 循环遍历链表只要 cur 不为 null就表示还未遍历到链表末尾。de.offer(cur);//将当前节点 cur 加入到双端队列 de 的尾部。cur cur.next;//将 cur 指针移动到下一个节点。}cur head;//重新指向链表的头节点int count 0;//用于记录当前选取节点的次数while (!de.isEmpty()){//只要双端队列 de 不为空说明还有节点需要处理继续循环。if (count % 2 0){//当 count 为偶数时从双端队列 de 的尾部取出一个节点将 cur 的 next 指针指向该节点pollLast() 方法会移除并返回队列的最后一个元素。cur.next de.pollLast();}else {//当 count 为奇数时从双端队列 de 的头部取出一个节点将 cur 的 next 指针指向该节点poll() 方法会移除并返回队列的第一个元素。cur.next de.poll();}cur cur.next;//将 cur 指针移动到新连接的节点以便进行下一次连接操作。count;//count 加 1记录选取节点的次数。}cur.next null;//当双端队列 de 为空时循环结束此时链表重排基本完成。但最后一个节点的 next 指针可能仍然指向原链表中的某个节点为了确保链表正确结束将 cur 的 next 指针置为 null。}
}
时间复杂度
1. 构建双端队列 方法首先遍历链表将所有节点除了头节点加入到双端队列中。这一遍历的时间复杂度为 O(n)其中n是链表中的节点数。 2. 重排链表 接下来方法进入一个循环直到双端队列为空。在每次迭代中它从队列的头部或尾部取出一个节点并将其链接到新的链表中。由于每个节点只处理一次这部分的时间复杂度也是 O(n)。 综合以上两个步骤整体的时间复杂度为O(n) O(n) O(n)
空间复杂度
1. 双端队列的存储 方法使用一个双端队列来存储所有节点除了头节点。在最坏的情况下这意味着需要存储 n-1个节点因此空间复杂度为 O(n)。 2. 其他变量 方法使用了一些额外的变量如 cur 和 count 这些变量占用的空间是常数级别的 O(1)。 因此总的空间复杂度主要由双端队列的存储决定O(n)
时间复杂度O(n)
空间复杂度O(n)
1 - 2 - 3 - 4 - 5
1. 初始化双端队列并存储节点
de 是一个双端队列用于存储链表中除头节点外的所有节点。cur 初始化为 head.next即指向节点 2。开始遍历链表 第一次循环cur 指向节点 2将节点 2 加入双端队列 de 的尾部然后 cur 移动到节点 3。第二次循环cur 指向节点 3将节点 3 加入双端队列 de 的尾部然后 cur 移动到节点 4。第三次循环cur 指向节点 4将节点 4 加入双端队列 de 的尾部然后 cur 移动到节点 5。第四次循环cur 指向节点 5将节点 5 加入双端队列 de 的尾部然后 cur 移动到 null循环结束。
此时双端队列 de 中的元素依次为 [2, 3, 4, 5]。
2. 重新定位指针并初始化计数器
cur 重新指向链表的头节点即节点 1。count 初始化为 0用于记录当前选取节点的次数。
3. 按规则重排链表
第一次循环count 0偶数 cur 指向节点 1从双端队列 de 的尾部取出节点 5将 cur节点 1的 next 指针指向节点 5。cur 移动到节点 5count 加 1 变为 1。此时双端队列 de 中的元素为 [2, 3, 4]。 第二次循环count 1奇数 cur 指向节点 5从双端队列 de 的头部取出节点 2将 cur节点 5的 next 指针指向节点 2。cur 移动到节点 2count 加 1 变为 2。此时双端队列 de 中的元素为 [3, 4]。 第三次循环count 2偶数 cur 指向节点 2从双端队列 de 的尾部取出节点 4将 cur节点 2的 next 指针指向节点 4。cur 移动到节点 4count 加 1 变为 3。此时双端队列 de 中的元素为 [3]。 第四次循环count 3奇数 cur 指向节点 4从双端队列 de 的头部取出节点 3将 cur节点 4的 next 指针指向节点 3。cur 移动到节点 3count 加 1 变为 4。此时双端队列 de 为空。
4. 处理链表结尾
此时双端队列 de 为空循环结束。将 cur节点 3的 next 指针置为 null确保链表正确结束。
最终重排后的链表为 1 - 5 - 2 - 4 - 3。
4.141. 环形链表
力扣题目链接(opens new window)
给定一个链表判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环我们使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。 如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
如果链表中存在环则返回 true 。 否则返回 false 。 思路
使用快慢指针法 分别定义 fast 和 slow指针从头结点出发fast指针每次移动两个节点slow指针每次移动一个节点如果 fast 和 slow指针在途中相遇 说明这个链表有环。
为什么fast 走两个节点slow走一个节点有环的话一定会在环内相遇呢而不是永远的错开呢
首先第一点 fast指针一定先进入环中如果fast 指针和slow指针相遇的话一定是在环中相遇。
为什么fast指针和slow指针一定会相遇呢
可以画一个环然后让 fast指针在任意一个节点开始追赶slow指针。
会发现最终都是这种情况 如下图 fast和slow各自再走一步 fast和slow就相遇了
这是因为fast是走两步slow是走一步其实相对于slow来说fast是一个节点一个节点的靠近slow的所以fast一定可以和slow重合。
动画如下 public class Circular_Linked_List {public static class ListNode {//ListNode 是一个静态内部类用于表示链表中的节点。int val;//存储节点的值。ListNode next;//指向下一个节点的引用。public ListNode(int i) {this.val i;}}public boolean hasCycle(ListNode head) {ListNode fast head;//fast 和 slow 指针都初始化为指向链表的头节点 head。fast 指针后续会以每次移动两步的速度遍历链表slow 指针则以每次移动一步的速度遍历链表。ListNode slow head;// 空链表、单节点链表一定不会有环while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if (fast slow) { // 快慢指针相遇表明有环return true;}}return false; // 正常走到链表末尾表明没有环}
}时间复杂度
在最坏的情况下快慢指针会遍历整个链表。快指针每次移动两步慢指针每次移动一步因此最多会遍历 n 个节点时间复杂度为 O(n)。
空间复杂度
只使用了常量级别的额外空间即两个指针 fast 和 slow 不随输入规模的变化而变化因此空间复杂度为 O(1)。
总结而言这段代码的时间复杂度为 O(n)空间复杂度为 O(1)。
无环链表 1 - 2 - 3 - 4
初始化fast 和 slow 指针都指向节点 1。 第一次循环 fast 指针移动两步指向节点 31 - 2 - 3。 slow 指针移动一步指向节点 21 - 2。 此时 fast 不等于 slow继续循环。 第二次循环 fast 指针尝试再移动两步但由于节点 4 的 next 为 nullfast.next.next 会导致 fast 变为 null不满足 while 循环条件fast ! null fast.next ! null循环结束。 返回结果由于循环正常结束说明链表没有环返回 false。 有环链表 1 - 2 - 3 - 4
初始化fast 和 slow 指针都指向节点 1。 第一次循环 fast 指针移动两步指向节点 31 - 2 - 3。 slow 指针移动一步指向节点 21 - 2。 此时 fast 不等于 slow继续循环。 第二次循环 fast 指针移动两步由于存在环节点 4 的 next 指向节点 2所以 fast 指向节点 23 - 4 - 2。 slow 指针移动一步指向节点 32 - 3。 此时 fast 不等于 slow继续循环。 第三次循环 fast 指针移动两步指向节点 42 - 3 - 4。 slow 指针移动一步指向节点 43 - 4。 此时 fast 等于 slow满足 if 条件返回 true表示链表有环。
5.面试题 02.07. 链表相交
同160.链表相交
力扣题目链接(opens new window)
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回 null 。
图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。
示例 1 示例 2 示例 3 思路
求两个链表交点节点的指针。 交点不是数值相等而是指针相等。
为了方便举例假设节点元素数值相等则节点指针相等。
看如下两个链表目前curA指向链表A的头结点curB指向链表B的头结点 我们求出两个链表的长度并求出两个链表长度的差值然后让curA移动到和curB 末尾对齐的位置如图 此时我们就可以比较curA和curB是否相同如果不相同同时向后移动curA和curB如果遇到curA curB则找到交点。否则循环退出返回空指针。
public class Intersection_of_Two_Linked_Lists {public static class ListNode {//ListNode 是一个静态内部类用于表示链表中的节点。int val;//存储节点的值。ListNode next;//指向下一个节点的引用。public ListNode(int i) {this.val i;}}public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {ListNode p1 headA, p2 headB;//p1 初始化为指向链表 headA 的头节点p2 初始化为指向链表 headB 的头节点。while (p1 ! p2) {//只要 p1 和 p2 不指向同一个节点就继续循环。当 p1 和 p2 相等时有两种情况一是找到了相交节点二是两个链表不相交此时 p1 和 p2 都为 null。if (p1 null) {//如果 p1 为 null说明 p1 已经遍历完链表 headA将 p1 重新指向链表 headB 的头节点开始遍历链表 headB。p1 headB;} else {//否则将 p1 移动到下一个节点p1 p1.next;}if (p2 null) {//如果 p2 为 null说明 p2 已经遍历完链表 headB将 p2 重新指向链表 headA 的头节点开始遍历链表 headA。p2 headA;} else {//否则将 p2 移动到下一个节点p2 p2.next;}}return p1;//当 while 循环结束时p1 和 p2 相等。如果两个链表相交p1 指向的就是相交节点如果两个链表不相交p1 和 p2 最终都会遍历完两个链表同时指向 null所以返回 p1}
}
时间复杂度
在最坏的情况下指针 p1 和 p2 会遍历两个链表的所有节点。这里 n 是链表 A 的长度 m 是链表 B 的长度。因此时间复杂度为 O(n m)。
空间复杂度
该算法只使用了固定数量的额外空间即两个指针 p1 和 p2 不随输入规模的变化而变化。因此空间复杂度为 O(1)。
时间复杂度O(n m)
空间复杂度O(1)
示例 1两个链表相交 假设存在两个相交链表 链表 headA1 - 2 - 3 - 6 - 7 链表 headB4 - 5 - 6 - 7 两个链表在节点 6 处相交。 初始化 p1 指向链表 headA 的头节点 1。 p2 指向链表 headB 的头节点 4。 第一次遍历 p1 依次经过节点 1、2、3、6、7然后 p1 变为 null根据逻辑将 p1 重新指向链表 headB 的头节点 4。 p2 依次经过节点 4、5、6、7然后 p2 变为 null根据逻辑将 p2 重新指向链表 headA 的头节点 1。 第二次遍历 p1 从节点 4 开始经过节点 5到达节点 6。 p2 从节点 1 开始经过节点 2、3到达节点 6。此时 p1 和 p2 相等while 循环结束。 返回结果返回 p1即节点 6这就是两个链表的相交节点。
示例 2两个链表不相交
假设存在两个不相交链表
链表 headA1 - 2 - 3链表 headB4 - 5
初始化 p1 指向链表 headA 的头节点 1。 p2 指向链表 headB 的头节点 4。 第一次遍历 p1 依次经过节点 1、2、3然后 p1 变为 null根据逻辑将 p1 重新指向链表 headB 的头节点 4。 p2 依次经过节点 4、5然后 p2 变为 null根据逻辑将 p2 重新指向链表 headA 的头节点 1。 第二次遍历 p1 从节点 4 开始经过节点 5然后 p1 又变为 null。 p2 从节点 1 开始经过节点 2、3然后 p2 也变为 null。此时 p1 和 p2 相等且都为 nullwhile 循环结束。 返回结果返回 p1即 null表示两个链表不相交。
