面试题52：两个链表的第一个公共节点
题目要求：
输入两个单链表，找出它们的第一个公共节点。以下图为例，对一个公共节点为6所在的节点。
1 -> 2 -> 3 -> 6 -> 7
4 -> 5 ↗
解题思路：
| 解法 | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 1 | 暴力求解 | o(mn) | o(1) |
| 2 | 分别存入两个栈，求栈中最深的相同节点 | o(m+n) | o(m+n) |
| 3 | 长链表先行|n-m|步，转化为等长链表 | o(m+n) | o(1) |
解法1：比较直接，不再赘述。
解法2：从链表的尾部向前看，发现尾部是相同的，向前走会分叉，找到分叉点即可。按照这个思路，如果这是双向链表，即得到尾节点并能够得到每个节点的前一个节点，那这个题就很简单了。对于单链表，本身是前节点->后节点，想要得到后节点->前节点，可以借助于栈的后进先出特性。两个单链表分别入栈，得到[1,2,3,6,7],[4,5,6,7]，然后不断出栈即可找到分叉点。
解法3：对于单链表，如果从头结点开始找公共节点，一个麻烦点是两个链表长度可能不一致，因此两个指针不同步（指两个指针无法同时指向公共点）。解决这个麻烦点，整个问题也就能顺利解决。那么，能否让两个链表长度一致？长链表先行几步即可，因为长链表头部多出的那几个节点一定不会是两链表的公共节点。以题目中的图为例，可以让1所在的链表先向前移动1个节点到2，这样就转化为求下面这两个链表的第一个公共节点：
2 -> 3 -> 6 -> 7
4 -> 5 ↗
一个指针指向2，另一个指向4，然后同时遍历，这应该很容易了吧。需要对两个链表先进行一次遍历求出长度，然后再同时遍历求公共点，时间复杂度o(n)，空间复杂度o(1)。
三种解法的代码实现如下。
package chapter5;
import structure.ListNode;
import java.util.Stack;
/**
* Created with IntelliJ IDEA
* Author: ryder
* Date : 2017/8/15
* Time : 10:28
* Description:两个链表的第一个公共节点
**/
public class P253_CommonNodesInLists {
//思路一：暴力解决，时间复杂度o(mn)，空间复杂度o(1)
//思路二：借助于两个栈，时间复杂度o(m+n)，空间复杂度o(m+n)
//思路三：转化为等长链表，时间复杂度o(m+n)，空间复杂度o(1)
public static ListNode<Integer> findFirstCommonNode(ListNode<Integer> head1,ListNode<Integer> head2){
for(ListNode<Integer> node1=head1;node1!=null;node1=node1.next){
for(ListNode<Integer> node2=head2;node2!=null;node2=node2.next){
if(node1==node2)
return node1;
}
}
return null;
}
public static ListNode<Integer> findFirstCommonNode2(ListNode<Integer> head1,ListNode<Integer> head2){
Stack<ListNode<Integer>> stack1 = new Stack<>();
Stack<ListNode<Integer>> stack2 = new Stack<>();
for(ListNode<Integer> node1=head1;node1!=null;node1=node1.next)
stack1.push(node1);
for(ListNode<Integer> node2=head2;node2!=null;node2=node2.next)
stack2.push(node2);
ListNode<Integer> commonNode = null;
while (!stack1.isEmpty() && !stack2.isEmpty()){
if(stack1.peek()==stack2.peek()){
commonNode = stack1.pop();
stack2.pop();
}
else
break;
}
return commonNode;
}
public static ListNode<Integer> findFirstCommonNode3(ListNode<Integer> head1,ListNode<Integer> head2){
ListNode<Integer> node1 = head1,node2 = head2;
int size1 = 0,size2 = 0;
for (;node1!=null;node1 = node1.next)
size1++;
for (;node2!=null;node2 = node2.next)
size2++;
node1 = head1;
node2 = head2;
while (size1>size2){
node1 = node1.next;
size1--;
}
while (size2>size1){
node2 = node2.next;
size2--;
}
while (node1!=null){
if(node1!=node2){
node1 = node1.next;
node2 = node2.next;
}
else
break;
}
return node1;
}
public static void main(String[] args){
// 1->2->3->6->7
// 4->5↗
ListNode<Integer> node1 = new ListNode<>(1);
ListNode<Integer> node2 = new ListNode<>(2);
ListNode<Integer> node3 = new ListNode<>(3);
ListNode<Integer> node4 = new ListNode<>(4);
ListNode<Integer> node5 = new ListNode<>(5);
ListNode<Integer> node6 = new ListNode<>(6);
ListNode<Integer> node7 = new ListNode<>(7);
node1.next = node2;
node2.next = node3;
node3.next = node6;
node4.next = node5;
node5.next = node6;
node6.next = node7;
ListNode<Integer> commonNode = findFirstCommonNode(node1,node4);
System.out.println(commonNode.val);
ListNode<Integer> commonNode2 = findFirstCommonNode2(node1,node4);
System.out.println(commonNode2.val);
ListNode<Integer> commonNode3 = findFirstCommonNode2(node1,node4);
System.out.println(commonNode3.val);
}
}
运行结果
6
6
6
