有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
思路
如果有汇合点，那么后面的个数肯定是一样的。所以先把长链表的往前移动，跟短链表一样长后，再挨个比较。如果找到 Node 对象相等说明是一样的，返回该对象；否则返回 Null。
时间复杂度为 O(n), 其中 n 为链表较长的。
空间复杂度为 O(n), 空间就是存储链表的数据。
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val) { this.val = val; }}
public class FindNode {
public ListNode find(ListNode nodeM, ListNode nodeN, int m, int n) {
ListNode smallNode = m > n ? nodeN : nodeM;
ListNode bigNode = m > n ? nodeM : nodeN;
int gap = Math.abs(m - n);
//移动bignode，直到等于smallnode的长度 while (gap > 0) { bigNode = bigNode.next; gap--; }
while (bigNode != null){ if (bigNode == smallNode) { return bigNode; }
bigNode = bigNode.next; smallNode = smallNode.next; }
return null; }}
复制代码
评论