2022一级造价停考_校园品牌推广方案_网上做推广怎么收费_外链网盘

前言

哎呀，去洗了点阳光青提（嚼嚼嚼），好吃！

一、反转链表（题目 206）

1. 题目描述

给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

2. 示例

示例 1：

输入：head = [1, 2, 3, 4, 5]

输出：[5, 4, 3, 2, 1]

解释：反转链表后，链表的顺序变为 [5, 4, 3, 2, 1]。

3. 解题思路

反转链表是链表操作中的基础题，主要考察对链表节点的操作。我们可以使用迭代的方法来反转链表。具体步骤如下：

1. 初始化三个指针：prev（前一个节点）、current（当前节点）、next（下一个节点）。
2. 遍历链表，将当前节点的 next 指针指向前一个节点。
3. 更新 prev 和 current 指针，向前移动。
4. 遍历结束后，prev 指针即为反转后的链表头节点。

4. 代码实现（Java）

public class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode current = head;while (current != null) {ListNode next = current.next;current.next = prev;prev = current;current = next;}return prev;}
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是链表的长度。我们只需要遍历链表一次。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

二、合并两个有序链表（题目 21）

1. 题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

2. 示例

示例 1：

输入：l1 = [1, 2, 4], l2 = [1, 3, 4]

输出：[1, 1, 2, 3, 4, 4]

解释：合并后的链表为 [1, 1, 2, 3, 4, 4]。

3. 解题思路

这道题主要考察链表的合并操作。我们可以使用双指针的方法来合并两个有序链表。具体步骤如下：

1. 初始化一个虚拟头节点 dummy，用于构建新的链表。
2. 使用两个指针 p1 和 p2 分别指向两个链表的头节点。
3. 比较 p1 和 p2 的值，将较小的节点添加到新链表中，并移动相应的指针。
4. 遍历结束后，将剩余的链表直接连接到新链表的末尾。

4. 代码实现（Java）

public class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode current = dummy;while (l1 != null && l2 != null) {if (l1.val < l2.val) {current.next = l1;l1 = l1.next;} else {current.next = l2;l2 = l2.next;}current = current.next;}current.next = (l1 != null) ? l1 : l2;return dummy.next;}
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是两个链表的总长度。我们只需要遍历两个链表一次。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

三、两数相加（题目 2）

1. 题目描述

给你两个按位逆序表示的非负整数 l1 和 l2，计算它们的和，并将结果以逆序的方式返回。

2. 示例

示例 1：

输入：l1 = [2, 4, 3], l2 = [5, 6, 4]

输出：[7, 0, 8]

解释：342 + 465 = 807，逆序表示为 [7, 0, 8]。

3. 解题思路

这道题主要考察链表的操作和进位的处理。我们可以从两个链表的头节点开始，逐位相加，并考虑进位的情况。具体步骤如下：

1. 初始化一个虚拟头节点 dummy，用于构建结果链表。
2. 使用两个指针 p1 和 p2 分别指向两个链表的头节点。
3. 初始化进位变量 carry 为 0。
4. 遍历链表，计算每一位的和，并处理进位。
5. 遍历结束后，如果还有进位，将进位作为一个新的节点添加到结果链表的末尾。

4. 代码实现（Java）

public class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode current = dummy;int carry = 0;while (l1 != null || l2 != null || carry != 0) {int sum = 0;if (l1 != null) {sum += l1.val;l1 = l1.next;}if (l2 != null) {sum += l2.val;l2 = l2.next;}sum += carry;carry = sum / 10;current.next = new ListNode(sum % 10);current = current.next;}return dummy.next;}
}

5. 复杂度分析

• 时间复杂度 ：O(max(m, n))，其中 m 和 n 分别是两个链表的长度。我们只需要遍历两个链表一次。
• 空间复杂度 ：O(max(m, n))，需要使用新的链表存储结果。

四、环形链表（题目 141）

1. 题目描述

给你一个链表的头节点 head，判断该链表是否为环形链表。

2. 示例

示例 1：

输入：head = [3, 2, 0, -4], index = 1

输出：true

解释：链表中存在环。

3. 解题思路

这道题主要考察链表中是否存在环。我们可以使用快慢指针的方法来判断。具体步骤如下：

1. 初始化两个指针 slow 和 fast，都指向链表的头节点。
2. slow 指针每次移动一步，fast 指针每次移动两步。
3. 如果 fast 指针或 fast.next 指针为 null，则链表中不存在环。
4. 如果 slow 指针和 fast 指针相遇，则链表中存在环。

4. 代码实现（Java）

public class Solution {public boolean hasCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {return true;}}return false;}
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是链表的长度。我们只需要遍历链表一次。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

五、环形链表 II（题目 142）

1. 题目描述

给你一个链表的头节点 head，返回链表的环的入口节点。如果链表中不存在环，则返回 null。

2. 示例

示例 1：

输入：head = [3, 2, 0, -4], index = 1

输出：[2, 0, -4]

解释：链表中存在环，入口节点为值为 2 的节点。

3. 解题思路

这道题主要考察链表中环的入口节点的查找。我们可以使用快慢指针的方法来找到环的入口节点。具体步骤如下：

1. 初始化两个指针 slow 和 fast，都指向链表的头节点。
2. slow 指针每次移动一步，fast 指针每次移动两步。
3. 如果 fast 指针或 fast.next 指针为 null，则链表中不存在环。
4. 如果 slow 指针和 fast 指针相遇，则链表中存在环。
5. 重新初始化一个指针 ptr 指向链表的头节点，slow 指针和 ptr 指针每次移动一步，直到它们相遇，相遇点即为环的入口节点。

4. 代码实现（Java）

public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;boolean hasCycle = false;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {hasCycle = true;break;}}if (!hasCycle) {return null;}ListNode ptr = head;while (ptr != slow) {ptr = ptr.next;slow = slow.next;}return ptr;}
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是链表的长度。我们只需要遍历链表一次。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

六、相交链表（题目 160）

1. 题目描述

给你两个单链表的头节点 headA 和 headB，判断两个链表是否相交，如果相交，返回相交的起始节点；如果不相交，返回 null。

2. 示例

示例 1：

输入：headA = [4, 1, 8, 4, 5], headB = [5, 6, 1, 8, 4, 5]

输出：[8, 4, 5]

解释：两个链表在节点值为 8 的节点处相交。

3. 解题思路

这道题主要考察链表的相交判断。我们可以使用双指针的方法来判断两个链表是否相交。具体步骤如下：

1. 初始化两个指针 pA 和 pB，分别指向两个链表的头节点。
2. 遍历两个链表，如果 pA 到达链表末尾，则将其指向 headB；如果 pB 到达链表末尾，则将其指向 headA。
3. 如果 pA 和 pB 相遇，则两个链表相交，返回相遇节点。
4. 如果遍历结束后仍未相遇，则两个链表不相交，返回 null。

4. 代码实现（Java）

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pA = headA;ListNode pB = headB;while (pA != pB) {pA = (pA == null) ? headB : pA.next;pB = (pB == null) ? headA : pB.next;}return pA;}
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是两个链表的总长度。我们只需要遍历两个链表一次。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

七、回文链表（题目 234）

1. 题目描述

给你一个单链表的头节点 head，判断该链表是否为回文链表。

2. 示例

示例 1：

输入：head = [1, 2, 2, 1]

输出：true

解释：链表是回文链表。

3. 解题思路

这道题主要考察链表的回文判断。我们可以使用快慢指针找到链表的中点，然后反转后半部分链表，最后比较前半部分和后半部分是否相同。具体步骤如下：

1. 使用快慢指针找到链表的中点。
2. 反转链表的后半部分。
3. 比较前半部分和后半部分是否相同。
4. 恢复链表的结构（可选）。

4. 代码实现（Java）

public class Solution {public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}// 找到链表的中点ListNode slow = head;ListNode fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}// 反转后半部分链表ListNode prev = null;ListNode current = slow.next;while (current != null) {ListNode next = current.next;current.next = prev;prev = current;current = next;}slow.next = null; // 断开链表// 比较前半部分和后半部分ListNode p1 = head;ListNode p2 = prev;boolean isPalindrome = true;while (p1 != null && p2 != null) {if (p1.val != p2.val) {isPalindrome = false;break;}p1 = p1.next;p2 = p2.next;}// 恢复链表结构current = prev;prev = null;while (current != null) {ListNode next = current.next;current.next = prev;prev = current;current = next;}slow.next = prev;return isPalindrome;}
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是链表的长度。我们只需要遍历链表一次。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

以上就是力扣热题 100 中与链表相关的经典题目的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。