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

目录

题目链接

题目

解题思路

代码

---

题目链接

两个链表的第一个公共结点_牛客题霸_牛客网

题目

解题思路

法一：（哈希表法）首先想到的是使用HashSet记录一个链表的指针,遍历另一个指针的时候第一次遇见的就是共同节点的第一个

法二：（双指针法）就是h1指针遍历一遍a后，再去遍历b;指针h2先遍历b,再去遍历a,因为两个指针同时开始,所以必能同时到达共同节点的起始位置处

代码

import java.util.*;
/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {ListNode dummyNode=new ListNode(-1);dummyNode.next=pHead1;HashSet<ListNode> st=new HashSet<>();ListNode cur=pHead1;while(cur!=null){st.add(cur);cur=cur.next;}cur=pHead2;while(cur!=null){if(st.contains(cur)){return cur;}cur=cur.next;}return null;}
}

法二：

import java.util.*;
/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {ListNode h1=pHead1,h2=pHead2;while(h1!=h2){h1=(h1==null)?pHead2:h1.next;h2=(h2==null)?pHead1:h2.next;}return h1;}
}