【题目描述】输入两个链表，找出它们的第一个公共结点。
注：默认为单链表，且无环
【解题思路】 //1.两个单链表若存在公共结点，则从第一个公共结点开始，后面的结点都是公共的。 //2.比较两个链表的长度。设置两个指针，分别指向两个链表的头结点。较长的链表的指针先走|len1-len2|步。然后两个指针同时向后移动，两个指针相遇时，即为两个链表的第一个公共结点。
public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if(pHead1==null || pHead2==null){ return null; } int len1=0, len2=0, i=0; ListNode p1=pHead1, p2=pHead2; //计算链表1的长度 while(p1.next!=null){ p1 = p1.next; len1++; } //计算链表2的长度 while(p2.next!=null){ p2 = p2.next; len2++; } p1=pHead1; p2=pHead2; if(len1>len2){ while(i<len1-len2){ p1 = p1.next; i++; } }else{ while(i<len2-len1){ p2 = p2.next; i++; } } while(p1 != p2){ p1 = p1.next; p2 = p2.next; } return p1; } }【解题思路2】走过你来时的路 //1. 设置两个指针，初始位置分别指向两个链表的头结点。 //2. 短链表的指针先走到尾结点，长链表的指针还未到达尾结点。然后，两个链表的长度差就自然的被两个指针的位置记录了下来。 //3. 将先到达尾结点的指针，移动到长链表的头结点位置。长链表指针到达尾部时，移动指针到锻炼表的头结点位置。同时向后走，两个指针必然相遇。 //4. 可能会出现的情况有： a.两个链表指针长度相同且存在公共结点，则第一次遍历的过程中即可求出第一个公共结点。 b.两个链表指针长度不同且存在公共结点，则第一次遍历得到两个链表的长度差，第二次遍历即可求出第一个公共结点。 c.两个链表无公共结点，则最后返回null
public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if(pHead1==null || pHead2==null){ return null; } ListNode p1=pHead1, p2=pHead2; while(p1!=p2){ p1 = (p1==null ? pHead2 : p1.next); p2 = (p2==null ? pHead1 : p2.next); } return p1; } }【解题思路3】 //1.运用HashMap来存储链表1的节点。 //2.遍历链表2，判断当前节点是否作为key已经在map中出现。若有，则返回该节点。若无，则继续遍历，直到结束，返回null
import java.util.HashMap; public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode current1 = pHead1; ListNode current2 = pHead2; HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>(); while (current1 != null) { hashMap.put(current1, null); current1 = current1.next; } while (current2 != null) { if (hashMap.containsKey(current2)) return current2; current2 = current2.next; } return null; } }【解题思路4】 如果存在共同节点的话，那么从该节点，两个链表之后的元素都是相同的。也就是说两个链表从尾部往前到某个点，节点都是一样的。 //1. 设置两个指针，初始化位置分别指向两个链表的头结点。 //2. 遍历每个链表，使得指针分别指向各自的尾部。 //3. 从尾部同时向前移动，若相同的最后一个节点，即为第一个公共结点。 //4. 借助栈来实现单链表的逆向访问。
链接：https://www.nowcoder.com/questionTerminal/6ab1d9a29e88450685099d45c9e31e46 来源：牛客网 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; } ListNode commonListNode = null; while (!stack1.isEmpty() && !stack2.isEmpty() && stack1.peek() == stack2.peek() ) { stack2.pop(); commonListNode = stack1.pop();; } return commonListNode; } }