问题概述

单链表定义如下：

public class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}

编写程序， 找出两个链表的交点。

如图所示，链表 A 和链表 B 在节点 8 处相交。

算法思路

首先确定一个事情：

如果两个链表有交点， 那么这两个链表的尾节点一定是相等的。

现在不仅需要判断是否有交点， 还需要找出这个节点。继续观察图形， 可以得出，如果两个链表相交，那么较长链表在往后移动 ($|length1-length2|$)个长度单位后，两个链表往后查找的速度一致，即可以用判断两个节点是否相等的方式来判断交点的位置了。
代码实现：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA==null||headB==null) {return null;}int l1 = getListNodeLength(headA);int l2 = getListNodeLength(headB);boolean aLargerThanB = l1>l2;//可以知道两个链表的长度int abs = aLargerThanB?(l1-l2):(l2-l1);if (abs!=0) {if (aLargerThanB) {while(abs>0) {headA = headA.next;abs--;}}else{while(abs>0) {headB = headB.next;abs--;}}}while (headA!=null) {if (headA==headB) {return headA;}headA = headA.next;headB = headB.next;}return null;}public int getListNodeLength(ListNode head) {int length = 0;while(head!=null) {length++;head = head.next;}return length;}

总结

以上是生活随笔为你收集整理的判断链表是否相交并找出交点的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。