题解 | #两个链表的第一个公共结点#

两个链表的第一个公共结点

http://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46

哈希集合
思路和算法
判断两个链表是否相交,可以使用哈希集合存储链表节点。
首先遍历链表 phead1,并将链表 phead1 中的每个节点加入哈希集合中。然后遍历链表 phead2,对于遍历到的每个节点,判断该节点是否在哈希集合中:如果当前节点不在哈希集合中,则继续遍历下一个节点;
如果当前节点在哈希集合中,则后面的节点都在哈希集合中,即从当前节点开始的所有节点都是两个链表的公共节点,因此在链表 phead2中遍历到的第一个在哈希集合中的节点就是两个链表的第一个公共节点,返回该节点。
如果链表phead2中的所有节点都不在哈希集合中,则两个链表不相交,返回 null。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        HashSet<ListNode> set = new HashSet<>();
        while(pHead1!=null){
            set.add(pHead1);
            pHead1 = pHead1.next;
        }
        while(pHead2!=null){
            if(set.contains(pHead2)){
                return pHead2;
            }
            pHead2 = pHead2.next;
        }
        return null;
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-23 18:25
点赞 评论 收藏
分享
点赞 评论 收藏
分享
Lorn的意义:1.你这根本就不会写简历呀,了解太少了 2.你这些项目经历感觉真的没啥亮点啊,描述的不行,重写书写一下让人看到核心,就继续海投 注意七八月份ofer还是比较多的,越往后机会越少,抓住时机,抓紧检查疏漏,加油查看图片
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务