面试算法：获取重合列表的第一个相交节点

本文主要是介绍面试算法：获取重合列表的第一个相交节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

更详细的讲解和代码调试演示过程，请参看视频
如何进入google,算法面试技能全面提升指南

给定两个单向链表，这两个链表有可能会有重叠，情况如下：

这里写图片描述

两个单向链表从节点5开始重合，要求给定一个空间复杂度为O(1)的算法，返回两个链表相交时的第一个节点。依据上图，也就是返回节点5.

首先我们需要做的是，确保给定的两个单向链表，他们是相交的。这个很好确定，只要从头遍历两个链表，如果他们的尾节点是一样的话，那么这两个链表就是相交的，问题是，如何尽快找到他们相交的第一个节点。

最笨的办法是，先找到尾节点，然后去掉尾节点，然后再次遍历查找新的尾节点，然后再去掉，直到两个链表没有共同的尾节点，那么最后去掉的共同尾巴节点，则是两个链表的首次相交节点。这种做法可行，但是算法复杂度是O(n^2)。有没有更好的办法呢？

假设第一个链表，从头结点到首次相交节点，所经历的距离用T1来表示，根据上图例子，T1 = 5, 也就是第一个队列从头结点0开始，需要经历节点1，2，3，4也就是总共5个节点后才能到达节点5.

我们用T3 表示队列2从头节点开始，到达首次相交节点的距离。根据上图，T3 = 3.

我们用T2表示两队列相交部分的节点数.依据上图T2 = 5.

由此队列1的长度为： T1 + T2 (1)
队列2的长度为：T3 + T2 (2)

如果我们能算出T3的数值，那么我们从队列2的头结点出发，经过T3-1步后，就能达到首次相交节点。我们如何计算T3的数值呢？

对T3的计算，需要一个小技巧.我们把队列2进行反转，得到下面情形：

这里写图片描述

如果此时我们从队列1的头结点开始进行遍历，那么从上头的节点0开始出发，会到队列2的头结点0结束。这样，在反转后，如果再次从头遍历队列1的话，得到的长度就是：

T1 + T3 + 1 (3).

根据上面三个公式，我们便可以计算出T3来。

(3) - (1) = T1 + T3 + 1 - T1 - T2 = T3 - T2 + 1
(3) - (1) + (2) = T3 - T2 + 1 + T3 + T2 = 2*T3 + 1

由此，我们可以反解出T3, 有了T3，我们便可以得到两队列首次相交节点了。

这个算法除了需要遍历两个队列外，还需要对其中一个队列进行反转，无论是遍历还是反转，其算法复杂度都是O(n), 因此总算法复杂度是O(n).

代码实现：


public class ListIntersetChecker {private Node listHead1;private Node listHead2;private int firstListLen = 0;  //t1 + t2private int secondListLen = 0; // t3 + t2private int lenAfterReverse = 0; // t1 + t3private ListReverse listReverse = null;public ListIntersetChecker(Node listHead1, Node listHead2) {this.listHead1 = listHead1;this.listHead2 = listHead2;}public Node getFirstIntersetNode() {if (isTwoListInterset() == false) {return null;}listReverse = new ListReverse(listHead2);Node reverseHead = listReverse.getReverseList();lenAfterReverse = getListLen(listHead1);int t3 = ((lenAfterReverse - firstListLen) + secondListLen - 1) / 2;int steps = secondListLen - t3 - 1;while (steps > 0) {reverseHead = reverseHead.next;steps--;}return reverseHead;}private int getListLen(Node head) {int len = 0;while (head != null) {head = head.next;len++;}return len;}private boolean isTwoListInterset() {Node head1 = listHead1;Node head2 = listHead2;while (head1.next != null || head2.next != null) {if (head1.next != null) {head1 = head1.next;firstListLen++; }if (head2.next != null) {head2 = head2.next;secondListLen++;}}firstListLen++;secondListLen++;return head1 == head2;}}

ListIntersetCheck.java 用于实现上面描述的算法。 getFirstIntersetNode返回两重叠队列首次相交节点。isTwoListInterset 用于判断两队列是否相交。在遍历两队列时，统计两队列的长度，也就是获得 T1 + T2 以及 T3 + T2的值。

然后把队列2进行反转，反转后，再从队列1的头节点进行遍历，得到的lenAfterReverse就是 T1 + T3 + 1.

int t3 = ((lenAfterReverse - firstListLen) + secondListLen - 1) / 2;
上面语句则根据前面的推导计算出T3.

由于队列2已经反转了，所以不能从队列2的头结点去遍历，只能从队列2的尾节点开始遍历，如果头结点开始遍历需要T3步的话，那么从尾节点遍历，则需要steps = secondListLen - (T3 + 1) 步。

由此，代码从队列2反转后的头结点开始，经过steps个节点后抵达两队列首次相交时的节点。

再看看主入口代码:


public class LinkList {public static void main(String[] args) {ListUtility util1 = new ListUtility();ListUtility util2 = new ListUtility();Node list1 = util1.createList(10);Node list2 = util2.createList(3);Node node = util1.getNodeByIdx(5);Node tail = util2.getNodeByIdx(2);tail.next = node;ListIntersetChecker intersetChecker = new ListIntersetChecker(list1, list2);Node interset = intersetChecker.getFirstIntersetNode();System.out.println("The first interset node is : " + interset.val);}
}