剑指OfferJZ36：两个链表的第一个公共结点-java版

NowCoder Offer 36： 两个链表的第一个公共结点 题目描述

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

输入： {1,2,3},{4,5},{6,7} 返回值： {6,7}

说明： 第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分 这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的 示例2

输入： {1},{2,3},{} 返回值： {}

说明： 2个链表没有公共节点 ,返回null，后台打印{}

解题思路

题目的意思是让我们找到比如上图两个单链表的第一个公共节点

解法一：使用栈

思路是从链表的尾部开始遍历（反向遍历），如果碰到有不一样节点的地方，就返回到上一次遍历的节点位置，这个节点就是两个链表的第一个公共节点

我们可以设置链表一从后往前遍历的节点为node1，链表二从后往前遍历的节点为node2，判断node1和node1这两个节点是否一样，

如果一样就说明当前位置的节点是公共节点， 如果不一样说明不是，那么上一次的节点就是我们要找的第一个公共节点

那么还有个问题，遍历单链表时只能从前往后遍历，如何反向遍历单链表呢？ 我们可以使用栈，利用栈Stack先进先出的特质： 将链表放入栈中，然后拿出来，从栈中拿出数据的过程正好是我们想要的反向遍历 比如把：1 2 3 4 5 6 7放入栈，拿出来就是7 6 5 4 3 2 1

public class jz36 {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        //定义两个栈
        Stack stack1 = new Stack();
        Stack stack2 = new Stack();

        //将两个链表分别放入栈中
        while(pHead1!=null){
            stack1.add(pHead1);
            pHead1=pHead1.next;
        }
        while(pHead2!=null){
            stack2.add(pHead2);
            pHead2=pHead2.next;
        }

        ListNode ans=null;//存放两个链表的公共节点
        //peek()函数返回栈顶的元素，但不弹出该栈顶元素
        //pop()函数返回栈顶的元素，并且将该栈顶元素出栈
        while(!stack1.isEmpty() && !stack2.isEmpty()){
            if(stack1.peek().val==stack2.peek().val){//说明当前节点是两个链表的公共节点
                ans=stack1.peek();//将公共节点存入ans中
                stack1.pop();
                stack2.pop();
            }else{//两个链表的节点不相等，此时上面ans里存放的值就是第一个公共节点
                break;
            }
        }
        return ans;
    }
}

解法二：减少遍历节点数（避免无效遍历，类似于前后双指针思想）

解法一另外开辟了两个栈空间，有些占用空间 现在不用另外开辟空间的思路是：

• 首先计算出两个链表的长度
• 如果长度相同，就从前往后同时同步遍历两个链表，直到某个位置两个链表的节点值相同时，这个节点就是这两个单链表的第一个公共节点
• 如果长度不同，就先遍历长的那个链表，让该链表的头节点先向后移动若干位，直到两个节点的长度相同为止，然后我们就可以如上同时遍历链表找公共节点了

代码实现

 public class jz36 {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {   
        //法二：
        int len1=0;
        int len2=0;

        //统计两个链表的长度
        ListNode removeNode1=pHead1;
        ListNode removeNode2=pHead2;
        while(removeNode1!=null){
            len1++;
            removeNode1=removeNode1.next;
        }
        while(removeNode2!=null){
            len2++;
            removeNode2=removeNode2.next;
        }

        //使两个链表长度相同
        if(len1>len2){
            for(int i=1;i