【链表】- 链表相交

1. 对应力扣题目连接

• 链表相交

2. 实现思路

• 链表详情：
  

考虑使用双指针：

解法一：

• 具体代码，详见3. 实现案例代码
• 解析：
  思路：因为链表按照如图的箭头走向，走的总路程是相等的，一定会相交于c点
  • 如图：
    
  • 如图：因为总的里程数相等一定会相交于c点，即：得到相交的节点8，作为头节点返回即可。

解法二：

• 待续：很快进行补充…

2. 实现案例代码

public class IntersectionOfLinkedLists {public static void main(String[] args) {// 示例链表：[4, 1, 8, 4, 5]ListNode headA = new ListNode(4);headA.next = new ListNode(1);ListNode intersectNode = new ListNode(8);headA.next.next = intersectNode;intersectNode.next = new ListNode(4);intersectNode.next.next = new ListNode(5);// 示例链表：[5, 0, 1, 8, 4, 5]ListNode headB = new ListNode(5);headB.next = new ListNode(0);headB.next.next = new ListNode(1);headB.next.next.next = intersectNode;// 找到相交节点ListNode result = getIntersectionNode(headA, headB);if (result != null) {System.out.println("Intersected at '" + result.val + "'");} else {System.out.println("No intersection");}}/*** 解法一：* @param headA* @param headB* @return*/public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}ListNode pA = headA;ListNode pB = headB;// 继续循环，直到两个指针相遇while (pA != pB) {// 如果 pA 到达末尾，将其重定位到 headBpA = (pA == null) ? headB : pA.next;// 如果 pB 到达末尾，将其重定位到 headApB = (pB == null) ? headA : pB.next;}// 当 pA == pB 时，要么是相交节点，要么是 nullreturn pA;}}