JAVA实现链表面试题(4)

11、判断两个单链表相交的第一个交点：

《编程之美》P193，5.3，面试题37就有这道题。

面试时，很碰到这道题的第一反应是：在第一个链表上排序数组每个节点，每遍历到一个结点的之后，在第二个链表上排序数组每个节点。如果在第二个链表上有一个结点和第一个链表上的节点一样，说明两个链表在这个节点上重叠。显然该方式的时间复杂度为O(len1 * len2)。

方法1：采用栈的模式

我们可以看出两个有公共节点而个别重合的数组，拓扑形状看起来像一个Y，而不也许是X型。 如下图所示：

如上图所示，如果单链表有公共节点，那么最后一个结点（结点7）一定是一样的，而且是从后面的某一个节点（结点6）开始，后续的结点都是一样的。

现在的难题是，在单链表中，我们没法从头节点开始排序数组，最后能够到达尾结点。最后到达的尾节点却要先被非常，这听上去是不是像“先进后出”？于是我们能够想到运用栈的特征来解决这个难题：分别把两个链表的节点放到两个栈中，这样两个链表的尾节点就位于两个栈的栈顶，接下来比较下一个栈顶，直到找到最后一个相同的节点。

这种模式中，我们应该运用两个辅助栈，空间复杂度是O(len1+len2)，时间复杂度是O(len1+len2)。和一起初的蛮力法相比，时间精度受到了提升，相当于是运用空间耗费换取时间强度。

那么，有没有更好的方式呢？接下来要讲。

方法2：判断两个链表相交的第一个结点：用到快慢指针，推荐（更优解）

我们在里面的方式2中，之所以用到栈，是因为我们想同时遍历到达两个链表的尾节点。其实为缓解这个难题我们也有一个更简单的方法：首先遍历两个链表得到他们的长度。在第二次遍历的之后，在较长的链表上走 |len1-len2| 步，接着再同时在两个链表上递归，找到的第一个相同的节点就是它们的第一个交点。

这种模式的时间复杂度也有O(len1+len2)，但是我们不再需要辅助栈，因此增加了空间效率。当面试官肯定了我们的最终一种思路的之后，就可以动手写代码了。

核心代码：

  //方法：求两个单链表相交的第一个交点
  public Node getFirstCommonNode(Node head1, Node head2) {
   if (head1 == null || head == null) {
    return null;
   }
 
   int length1 = getLength(head1);
   int length2 = getLength(head2);
   int lengthDif = 0; //两个链表长度的差值
   Node longHead;
   Node shortHead;
 
   //找出较长的那个链表
   if (length1 > length2) {
    longHead = head1;
    shortHead = head2;
    lengthDif = length1 - length2;
   } else {
    longHead = head2;
    shortHead = head1;
    lengthDif = length2 - length1;
   }
 
   //将较长的那个链表的指针向前走length个距离
   for (int i = 0; i < lengthDif; i++) {
    longHead = longHead.next;
   }
 
   //将两个链表的指针同时向前移动
   while (longHead != null && shortHead != null) {
    if (longHead == shortHead) { //第一个相同的结点就是相交的第一个结点
     return longHead;
    }
    longHead = longHead.next;
    shortHead = shortHead.next;
   }
 
   return null;
  }
 
 
  //方法：获取单链表的长度
  public int getLength(Node head) {
   if (head == null) {
    return 0;
   }
 
   int length = 0;
  Node current = head;   while (current != null) {
 
    length++;
    current = current.next;
   }
 
   return length;

以上就是有关java数组的经典面试题目，希望可以帮助你们成功借助面试。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-122053-4.html