链表

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
^
cur

2. 统计链表长度

• 第一次循环：cur 指向值为 1 的节点，len 加 1 变为 1，cur 移动到下一个节点（值为 2 的节点）。
• 第二次循环：cur 指向值为 2 的节点，len 加 1 变为 2，cur 移动到下一个节点（另一个值为 2 的节点）。
• 第三次循环：cur 指向值为 2 的节点，len 加 1 变为 3，cur 移动到下一个节点（值为 1 的节点）。
• 第四次循环：cur 指向值为 1 的节点，len 加 1 变为 4，cur 移动到 null，循环结束。

此时得到链表长度 len = 4。

3. 将链表元素存储到数组中

• cur 重新指向链表的头节点（值为 1 的节点）。
• 创建长度为 4 的整型数组 res。
• 第一次循环：i = 0，res[0] 赋值为 cur 指向节点的值 1，cur 移动到下一个节点（值为 2 的节点）。
• 第二次循环：i = 1，res[1] 赋值为 cur 指向节点的值 2，cur 移动到下一个节点（另一个值为 2 的节点）。
• 第三次循环：i = 2，res[2] 赋值为 cur 指向节点的值 2，cur 移动到下一个节点（值为 1 的节点）。
• 第四次循环：i = 3，res[3] 赋值为 cur 指向节点的值 1，cur 移动到 null，循环结束。

此时数组 res 中的元素为 [1, 2, 2, 1]。

4. 使用双指针法比较数组对称位置的元素

• 第一次比较：i = 0，j = 3，res[0] = 1，res[3] = 1，两者相等，继续循环。
• 第二次比较：i = 1，j = 2，res[1] = 2，res[2] = 2，两者相等，继续循环。
• 此时 i = 2，j = 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) {Deque<ListNode> 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 移动到节点 5，count 加 1 变为 1。此时双端队列 de 中的元素为 [2, 3, 4]。
• 第二次循环（count = 1，奇数）：
  • cur 指向节点 5，从双端队列 de 的头部取出节点 2，将 cur（节点 5）的 next 指针指向节点 2。
  • cur 移动到节点 2，count 加 1 变为 2。此时双端队列 de 中的元素为 [3, 4]。
• 第三次循环（count = 2，偶数）：
  • cur 指向节点 2，从双端队列 de 的尾部取出节点 4，将 cur（节点 2）的 next 指针指向节点 4。
  • cur 移动到节点 4，count 加 1 变为 3。此时双端队列 de 中的元素为 [3]。
• 第四次循环（count = 3，奇数）：
  • cur 指向节点 4，从双端队列 de 的头部取出节点 3，将 cur（节点 4）的 next 指针指向节点 3。
  • cur 移动到节点 3，count 加 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 指针移动两步，指向节点 3（1 -> 2 -> 3）。
slow 指针移动一步，指向节点 2（1 -> 2）。
此时 fast 不等于 slow，继续循环。
第二次循环：
fast 指针尝试再移动两步，但由于节点 4 的 next 为 null，fast.next.next 会导致 fast 变为 null，不满足 while 循环条件（fast != null && fast.next != null），循环结束。
返回结果：由于循环正常结束，说明链表没有环，返回 false。
有环链表 1 -> 2 -> 3 -> 4

初始化：fast 和 slow 指针都指向节点 1。
第一次循环：
fast 指针移动两步，指向节点 3（1 -> 2 -> 3）。
slow 指针移动一步，指向节点 2（1 -> 2）。
此时 fast 不等于 slow，继续循环。
第二次循环：
fast 指针移动两步，由于存在环，节点 4 的 next 指向节点 2，所以 fast 指向节点 2（3 -> 4 -> 2）。
slow 指针移动一步，指向节点 3（2 -> 3）。
此时 fast 不等于 slow，继续循环。
第三次循环：
fast 指针移动两步，指向节点 4（2 -> 3 -> 4）。
slow 指针移动一步，指向节点 4（3 -> 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：两个链表相交
假设存在两个相交链表：
链表 headA：1 -> 2 -> 3 -> 6 -> 7
链表 headB：4 -> 5 -> 6 -> 7
两个链表在节点 6 处相交。

1. 初始化：

   • p1 指向链表 headA 的头节点 1。

   • p2 指向链表 headB 的头节点 4。

2. 第一次遍历：

   • p1 依次经过节点 1、2、3、6、7，然后 p1 变为 null，根据逻辑将 p1 重新指向链表 headB 的头节点 4。

   • p2 依次经过节点 4、5、6、7，然后 p2 变为 null，根据逻辑将 p2 重新指向链表 headA 的头节点 1。

3. 第二次遍历：

   • p1 从节点 4 开始，经过节点 5，到达节点 6。

   • p2 从节点 1 开始，经过节点 2、3，到达节点 6。此时 p1 和 p2 相等，while 循环结束。

4. 返回结果：返回 p1，即节点 6，这就是两个链表的相交节点。

示例 2：两个链表不相交

假设存在两个不相交链表：

• 链表 headA：1 -> 2 -> 3
• 链表 headB：4 -> 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 相等且都为 null，while 循环结束。
返回结果：返回 p1，即 null，表示两个链表不相交。