合并两个单向链表

1．有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。

请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。





思路：

长链表向后移动链表长度差值，然后循环比较两个链表的头部指针是否相等，如果相等则返回；不相同，长短链表均向后移动。

时间复杂度：O(max(m,n))，即最长的链表长度

空间复杂度：O(1)，未申请新空间

findMergeNode(list1, list2)：

int m = list1.length;

int n = list2.lenth;

longLinkedList = m>n?list1:list2;

shortLinkedList = m>n?list2:list2;

int k = Math.abs(m-n);

while(k > 0)

{

longLinkedList = longLinkedList.next;

k--;

}

while(longLinkedList.hasNext())

{

If(longLinkedList == shortLinkedList){

    Return;

}

longLinkedList = longLinkedList.next;

shortLinkedList = shortLinkedList.next;