更详细的讲解和代码调试演示过程，请参看视频
如何进入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 + t2
private int secondListLen = 0; // t3 + t2
private int lenAfterReverse = 0; // t1 + t3
private 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);
}
}
程序启动时，先构造两个队列，队列1节点从0到9，队列2从0到2，然后把队列2的尾节点的next指向队列1的编号为5的节点，于是就构造了我们例子图中的两个相交队列，然后再利用ListIntersetChecker获得两重合队列的首个相交节点。
最后程序运行结果为：
The first interset node is : 5
结果跟我们理论推导一致，也就是说，我们的说法实现是正确的。更详细的代码讲解和推导调试过程，请参看视频。
更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：
这里写图片描述
网友评论