双链表找相交结点

思路：

遍历两个双链表，分别求出它们的长度（节点数）。如果两个链表相交，它们在交点之后的部分长度应该是一样的。因此，可以计算出两个链表的长度差（如果有的话），并且让较长的链表先向前移动长度差个结点，使得它们处于相同的长度上。接下来，同时遍历两个链表，比较它们的结点是否相同。当找到第一个相同的结点时，即为相交结点。如果两个链表不相交，它们将在尾部同时到达 null，此时可以返回 null 表示没有相交结点。

实现上述思路：

import org.junit.jupiter.api.Test; import static org.junit.jupiter.api.Assertions.assertEquals; class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; this.next = null; } } public class IntersectionOfTwoLinkedLists { // 查找相交结点的方法 public ListNode findIntersection(ListNode headA, ListNode headB) { int lenA = getLength(headA); int lenB = getLength(headB); // 将较长链表前移，使它们处于相同长度上 while (lenA > lenB) { headA = headA.next; lenA--; } while (lenB > lenA) { headB = headB.next; lenB--; } // 同时遍历链表，找到第一个相交结点 while (headA != null && headB != null) { if (headA == headB) { return headA; } headA = headA.next; headB = headB.next; } return null; } // 辅助方法：计算链表长度 private int getLength(ListNode head) { int length = 0; while (head != null) { length++; head = head.next; } return length; } // 单元测试 @Test public void testFindIntersection() { // 创建两个链表 ListNode commonNode = new ListNode(4); commonNode.next = new ListNode(5); ListNode headA = new ListNode(1); headA.next = new ListNode(2); headA.next.next = commonNode; ListNode headB = new ListNode(3); headB.next = commonNode; IntersectionOfTwoLinkedLists solution = new IntersectionOfTwoLinkedLists(); // 测试方法 ListNode intersection = solution.findIntersection(headA, headB); // 验证结果 assertEquals(4, intersection.val); } }