Java实现有序集合合并与交集算法（顺序表+单链表）

### 📌 1. 顺序表合并（递增有序并集） **算法思路**： 利用双指针遍历两个有序顺序表，比较当前元素大小，将较小者加入结果表，若相等则只加入一次。时间复杂度为 *O(m+n)*。 ```java import java.util.Arrays; public class OrderedListMerge { public static int[] mergeOrderedArrays(int[] A, int[] B) { int i = 0, j = 0, k = 0; int[] C = new int[A.length + B.length]; // 预分配最大可能空间 while (i < A.length && j < B.length) { if (A[i] < B[j]) { C[k++] = A[i++]; } else if (A[i] > B[j]) { C[k++] = B[j++]; } else { C[k++] = A[i++]; // 相等时只保留一个 j++; } } // 复制剩余元素 while (i < A.length) C[k++] = A[i++]; while (j < B.length) C[k++] = B[j++]; // 返回实际长度数组（Java需手动处理） return Arrays.copyOf(C, k); } public static void main(String[] args) { int[] A = {1, 3, 5, 7}; int[] B = {1, 2, 4, 5, 7}; int[] C = mergeOrderedArrays(A, B); System.out.println("并集结果: " + Arrays.toString(C)); // [1, 2, 3, 4, 5, 7] } } ``` **关键点**： - 使用 `Arrays.copyOf` 截断未使用的数组空间。 - 测试用例验证了重复元素处理逻辑。 --- ### 📌 2. 单链表求交（原地操作） **算法思路**： 双指针遍历两个链表，当元素相等时加入结果链表（通过修改指针），否则移动较小元素的指针。时间复杂度 *O(m+n)*，空间复杂度 *O(1)*。 ```java class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class OrderedListIntersection { public static ListNode getIntersection(ListNode A, ListNode B) { ListNode dummy = new ListNode(0); // 虚拟头节点简化操作 ListNode tail = dummy; while (A != null && B != null) { if (A.val < B.val) { A = A.next; } else if (A.val > B.val) { B = B.next; } else { tail.next = A; // 直接复用A的节点 tail = tail.next; A = A.next; B = B.next; tail.next = null; // 断开原链表后续连接 } } return dummy.next; } // 辅助方法：打印链表 public static void printList(ListNode head) { while (head != null) { System.out.print(head.val + " "); head = head.next; } System.out.println(); } public static void main(String[] args) { // 构建测试链表 A: 1->3->5->7 ListNode A = new ListNode(1); A.next = new ListNode(3); A.next.next = new ListNode(5); A.next.next.next = new ListNode(7); // 构建测试链表 B: 1->2->4->5->7 ListNode B = new ListNode(1); B.next = new ListNode(2); B.next.next = new ListNode(4); B.next.next.next = new ListNode(5); B.next.next.next.next = new ListNode(7); ListNode C = getIntersection(A, B); System.out.print("交集结果: "); printList(C); // 1 5 7 } } ``` **关键点**： - **原地操作**：直接复用 `A` 链表的节点，避免新建节点。 - **断开连接**：每次添加节点后需将其 `next` 置为 `null`，防止原链表后续节点被意外包含。 - **虚拟头节点**：简化链表头部插入操作。 --- ### 🚀 开发建议 1. **边界检查**：处理空链表/数组时需提前返回。 2. **泛型支持**：可将 `int` 改为泛型 `<T extends Comparable<T>>` 以支持更多数据类型。 3. **单元测试**：补充测试用例（如完全不重叠、完全重叠、包含负数等）。 4. **性能优化**：顺序表合并时若已知两表长度差异大，可优先遍历较短表。 ######[AI写代码神器 | 1247点数解答 | 2026-03-25 10:35:22]