剑指offer

36 两个链表的第一个公共节点

题目描述

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

输入：

链表一：1–2–3–6–7–8
链表二：4–5–6–7–8

输出：

则第一个公共节点为6。

思路

如果两个链表有公共结点，那么公共结点出现在两个链表的尾部。如果我们从两个链表的尾部开始往前比较，最后一个相同的结点就是我们要找的结点。
But，在单链表中只能从头结点开始按顺序遍历，最后才能到达尾结点。最后到达的尾结点却要最先被比较，这是“后进先出”的特性。可以利用栈求解。

方法一：可利用 hashmap 的特性求解

import java.util.HashMap;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

        //方法一：运用HasnMap的特性
        HashMap<ListNode, Integer> map = new HashMap<ListNode, Integer>();
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;

        while(cur1!=null){
            map.put(cur1,1);
            cur1 = cur1.next;
        }

        while(cur2!=null){
            if(map.containsKey(cur2))
                return cur2;
            cur2 = cur2.next;
        }

        return null;
    }
}

方法二：让两个指针距离表尾相同

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

        //方法二：用两个指针扫描”两个链表“，最终两个指针到达 null 或者到达公共结点。
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        while(cur1!=cur2){
            cur1 = (cur1==null ? pHead2 : cur1.next);
            cur2 = (cur2==null ? pHead1 : cur2.next);
        }
        return cur1;
    }
}