第2天：链表算法 - 问题分析与Java实现
1. 问题分析
问题1：反转链表
问题描述
给定一个单链表的头节点 head，反转该链表并返回其头节点。
示例
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
2. 解决方案（多种方法）
方法1：迭代法（O(n))
思路：
- 遍历链表，同时反转每个节点的指针。
- 使用三个指针：
prev、current和next来跟踪节点并反转链表。
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; // 返回新的头节点
}
优点：
- 时间复杂度：O(n)，n为链表的节点数量。
- 空间复杂度：O(1)，只使用了常量级别的额外空间。
方法2：递归法（O(n))
思路：
- 使用递归来反转剩余的链表，并在递归回溯时调整指针。
public ListNode reverseListRecursive(ListNode head) {if (head == null || head.next == null) {return head;}ListNode reversedList = reverseListRecursive(head.next);head.next.next = head;head.next = null;return reversedList;
}
优点：
- 时间复杂度：O(n)，递归遍历链表的每个节点。
- 空间复杂度：O(n)，由于递归栈的使用。
问题2：判断链表是否有环（弗洛伊德快慢指针法）
问题描述
给定一个链表，判断它是否有环。
示例
Input: head = [3,2,0,-4], pos = 1
Output: true
解释：链表中存在环，尾节点连接到索引为1的节点。
2. 解决方案（多种方法）
方法1：弗洛伊德快慢指针法（O(n))
思路：
- 使用两个指针，一个慢指针（
slow）和一个快指针（fast）。 - 如果链表中有环，快指针会追上慢指针。
public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}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;
}
优点：
- 时间复杂度：O(n)，快慢指针各自遍历链表一次。
- 空间复杂度：O(1)，没有额外空间的使用。
方法2：HashSet法（O(n))
思路：
- 使用一个
HashSet来存储已访问过的节点。如果遇到重复的节点，就说明有环。
import java.util.HashSet;public boolean hasCycleHashSet(ListNode head) {HashSet<ListNode> visitedNodes = new HashSet<>();while (head != null) {if (visitedNodes.contains(head)) {return true;}visitedNodes.add(head);head = head.next;}return false;
}
优点：
- 时间复杂度：O(n)，遍历链表一次。
- 空间复杂度：O(n)，由于存储了链表节点的集合。
问题3：合并两个有序链表
问题描述
将两个有序链表合并为一个新的有序链表，并返回合并后的链表。
示例
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
2. 解决方案（多种方法）
方法1：迭代法（O(n))
思路：
- 同时遍历两个链表，比较每个节点的值，将较小的节点加入到新的链表中。
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;}if (l1 != null) {current.next = l1;} else {current.next = l2;}return dummy.next; // 返回合并后的链表
}
优点：
- 时间复杂度：O(n)，n为两个链表节点的总数。
- 空间复杂度：O(1)，仅使用指针来遍历链表。
方法2：递归法（O(n))
思路：
- 使用递归的方式合并两个链表，每次比较两个链表的头节点。
public ListNode mergeTwoListsRecursive(ListNode l1, ListNode l2) {if (l1 == null) return l2;if (l2 == null) return l1;if (l1.val < l2.val) {l1.next = mergeTwoListsRecursive(l1.next, l2);return l1;} else {l2.next = mergeTwoListsRecursive(l1, l2.next);return l2;}
}
优点：
- 时间复杂度：O(n)，递归遍历两个链表。
- 空间复杂度：O(n)，递归栈的空间开销。
总结
| 问题 | 最优方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 反转链表 | 迭代法 | O(n) | O(1) |
| 判断环 | 弗洛伊德法 | O(n) | O(1) |
| 合并有序链表 | 迭代法 | O(n) | O(1) |
🔥 掌握这些链表算法，提升你的面试能力，顺利应对大厂面试！ 🚀
