如何实现两个链表的交叉合并？

## 作用 交叉合并是将两个链表的节点交替连接，例如： - `l1: 1 -> 2 -> 3` - `l2: 6 -> 5 -> 4` - 合并结果：`1 -> 6 -> 2 -> 5 -> 3 -> 4` 在重排链表问题中，先把原链表从中间拆成前后两部分，再将后半部分反转，最后对两部分做交叉合并。 ## 原理 ### 1. 找到链表中间节点 使用快慢指针： - `slow` 每次走一步 - `fast` 每次走两步 - 当 `fast` 到达链表末尾时，`slow` 位于中间位置 ```java ListNode slow = head, fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } ``` ### 2. 从中间拆分链表 - 前半部分从 `head` 开始 - 后半部分从中间节点的 `next` 开始 - 将中间节点的 `next` 置为 `null`，完成截断 ```java ListNode l1 = head; ListNode l2 = middleNode.next; middleNode.next = null; ``` ### 3. 反转后半部分链表 使用三个指针 `prev`、`curr`、`nxt` 逐个反转节点指向： ```java ListNode prev = null, curr = head; while (curr != null) { ListNode nxt = curr.next; curr.next = prev; prev = curr; curr = nxt; } return prev; ``` ### 4. 交替合并两个链表 每轮先保存两个链表当前节点的后继节点，然后修改指针： - `l1.next = l2` - `l2.next = l1` - 再分别移动到之前保存的后继节点 ```java while (l1 != null && l2 != null) { ListNode p1 = l1.next; ListNode p2 = l2.next; l1.next = l2; l1 = p1; l2.next = l1; l2 = p2; } ``` 当其中一个链表遍历结束时停止。由于前半部分长度通常不小于后半部分，剩余节点会自然接在结果链表末尾，无需额外处理。

## 作用 该方法用于求两个链表的相交节点。这里判断的是节点指针是否相同，即两个链表是否指向同一个节点，而不是节点中的数值相等。 ## 原理一：统计长度，尾部对齐 1. 分别遍历链表 A 和链表 B，求出它们的长度 `lenA`、`lenB`。 2. 让指向较长链表的指针先移动两个链表的长度差，使两个指针在尾部对齐。 3. 然后同时移动两个指针，逐个比较节点是否相同。 4. 如果两个指针相等，则该节点就是相交节点。 5. 如果遍历结束仍未相等，说明两个链表不相交，返回空。 - 时间复杂度：`O(n + m)` - 空间复杂度：`O(1)` ## 原理二：双指针交替遍历 1. 使用两个指针分别从链表 A、B 的头节点开始遍历。 2. 当一个指针遍历完当前链表后，切换到另一个链表的头节点继续遍历。 3. 如果两个链表存在交点，两个指针最终走过的总长度相同，会在交点处相遇。 4. 如果没有交点，两个指针最终都会变为空，此时返回空。 核心逻辑是：指针 A 走完 A 后走 B，指针 B 走完 B 后走 A，从而消除两个链表长度不同带来的步数差。