《剑指offer》 第52题 两个链表的第一个公共结点

题目描述
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

本题最容易想到的肯定是最暴力的方法：拿某一个链表的元素，去和另一个链表的所有节点匹配，然后再换一个，再拿去全部匹配一次。这样的时间复杂度肯定不会让你拿到offer。所以要优化啊。
  如果经常用Java刷题的话，本题肯定也会想到使用Hash表来判断是否重复。虽然是个方法，但总使用工具类解决，在面试中不占便宜。
  本题要深入本质才行，一旦两个链表有公共结点，就意味着两个链表可能不止有一个公共节点。两个链表在6处开始公共，则意味着6后面的所有节点都是公共的了。注意{1，4，5}和{1，3，7}中的1并不是公共节点，因为这两个节点只是val这个属性相同，next属性是不同的

解法很多，在不使用工具类时，先上个暴力的：

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
       while(pHead1 != null){
            ListNode node = pHead2;//用一个指针用来遍历第二个链表
            while(node != null){
                if(pHead1 == node){//相同就返回这个节点
                    return node;
                }
                node = node.next;//否则就换下一个节点（第二个链表）
            }
            pHead1 = pHead1.next;//没有相同的，比较下一个节点（第一个链表）
        }
      return null;
    }
}

思路1：

  使用栈的方法，也就是用两个辅助栈，分别装两个链表，装完后，栈顶元素肯定相同，这个时候就两个栈同时弹出栈顶元素，直到栈顶不再相同时，就说明刚刚弹出的就是第一次相同的节点（比如上图中，分别入两个栈后，两个栈顶都是7，同时弹，这时再弹6，就发现一个栈顶是5，一个是3，不相同了，就返回6）。

import java.util.Stack;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    if (pHead1 == null || pHead2 == null) {
            return null;
        }
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();

        while (pHead1 != null) {
            stack1.push(pHead1);
            pHead1 = pHead1.next;
        } 
        while (pHead2 != null) {
            stack2.push(pHead2);
            pHead2 = pHead2.next;
        }
 //Stack中装的是节点，因此不能比值，应该比节点。之前也说过，只是某个属性相同的节点不能算公共的
//==是比较对象的地址
        ListNode Node = null;
        while(!stack1.isEmpty() && !stack2.isEmpty() && stack1.peek()==stack2.peek()){
            stack2.pop();
            Node = stack1.pop();;
        }
        return Node;
    }
}

思路2：

  利用两个指针：一个指针顺序遍历list1和list2，另一个指针顺序遍历list2和list1，（这样两指针能够保证最终同时走到尾结点），两个指针找到的第一个相同结点就是第一个公共结点。过程，如上图的两个链表，遍历过程是（1,2,3,6,7,4,5,6,7）另一个指针的遍历顺序是（4,5,6,7,1,2,3,6,7），可以看到两个链表的遍历长度一样，且步调也一致时。最终会在6碰面。因此，代码中的过程就是，list1遍历完后，开始遍历list2，另一个则是list2遍历完后，开始遍历list1。
  相比于其他方法，这个方法的细节比较多。我是觉得如果不熟悉，在面试的时候不容易写出来。看似精短，实则不容易看懂。
  写法过程见注释

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null)
            return null;
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while(p1!=p2){//不相同肯定要分别移动到下一个
            p1 = p1.next;
            p2 = p2.next;
            if(p1 != p2){//如果相同，跳过。
//只有节点不同，且移动到null时，才需要换接另一个链表。但是两者都为null时，需要直接返回
//所以才必须加一个p1和p2相等的判断
                if(p1 == null)
                    p1 = pHead2;
                if(p2 == null)
                    p2 = pHead1;
            }
        }
        return p1;
    }
}

思路3：

快慢指针的方法。先遍历两次链表，然后统计节点数，让快指针先走完两个链表的差距，然后两个链表在同一起跑线上移动并比较（剩下的节点数一样）。这个方法和思路2有点相似，都是调整到数量相同且步调一致的时候比较。

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode curNode1 = pHead1;
        ListNode curNode2 = pHead2;
        // 算 pHead1 长度
        int len1 = 0;
        while (curNode1 != null) {
          len1++;
          curNode1 = curNode1.next;
        }
        // 算 pHead2 长度
        int len2 = 0;
        while (curNode2 != null) {
          len2++;
          curNode2 = curNode2.next;
        }
        // 快慢指针开始缩短两个链表的差距了
        curNode1 = pHead1;
        curNode2 = pHead2;
        if (len1 >= len2) {//第一个链表比较长时
          for (int i = 0; i < len1 - len2; i++) {
            curNode1 = curNode1.next;
          }
        } else {//第2个链表比较长时
          for (int i = 0; i < len2 - len1; i++) {
            curNode2 = curNode2.next;
          }
        }
        while (curNode1 != curNode2) {//同一起跑线了
          curNode1 = curNode1.next;
          curNode2 = curNode2.next;
        }
        return curNode1;
    }
}