作业：有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
采用双指针法：分别为链表 A 和链表 B 设置指针 A 和指针 B，然后开始遍历链表，如果遍历完当前链表，则将指针指向另外一个链表的头部继续遍历，直至两个指针相遇。
最终两个指针分别走过的路径为：
指针 A :a+c+b
指针 B :b+c+a
明显 a+c+b = b+c+a,因而如果两个链表相交，则指针 A 和指针 B 必定在相交结点相遇。
复杂度分析
时间复杂度 : O(m+n)
空间复杂度 : O(1)
代码如下：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //tempA和tempB我们可以认为是A,B两个指针 ListNode tempA = headA; ListNode tempB = headB; while (tempA != tempB) { //如果指针tempA不为空，tempA就往后移一步。 //如果指针tempA为空，就让指针tempA指向headB（注意这里是headB不是tempB） tempA = tempA == null ? headB : tempA.next; //指针tempB同上 tempB = tempB == null ? headA : tempB.next; } //tempA要么是空，要么是两链表的交点 return tempA; }}
复制代码
评论