米哈游大数据面试题及参考答案

怎么判断两个链表是否相交？怎么优化？

判断两个链表是否相交可以采用多种方法。

一种方法是使用双指针。首先分别遍历两个链表，得到两个链表的长度。然后让长链表的指针先走两个链表长度差的步数。之后，同时移动两个链表的指针，每次比较两个指针是否指向相同的节点。如果指向相同节点，那么这两个链表相交；如果直到指针都走到链表末尾还没有相同节点，那么这两个链表不相交。

  // ListNode 定义static class ListNode {int val;ListNode next;ListNode(int x) { val = x; }}public boolean isIntersect(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return false;}// 1. 计算两个链表的长度int lenA = getLength(headA);int lenB = getLength(headB);// 2. 让较长的链表先走一段距离，使得两个链表剩余部分长度相同while (lenA >