剑指offer系列之35：两个链表的第一个公共节点_剑指offer.35.两个链表的公共节点-CSDN博客

本文链接：https://blog.csdn.net/ly_main/article/details/51136326

本文介绍了一种算法，用于找到两个单向链表的第一个公共节点。提供了两种思路：一是利用栈从链表尾部开始比较；二是计算两链表长度差，让较长链表先走差值再同步比较。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目描述：输入两个链表，找出它们的第一个公共节点。

两个有公共节点的单向链表的特点：如果两个链表有公共节点，那么这两个链表从某一节点开始，它们的m_pNext指针指向同一个节点，而且从第一个公共节点开始，之后它们的所有节点都是重合的，拓扑形状向Y,而不可能像X.
思路1：如果两个链表有公共的节点，则公共的节点出现在链表的尾部，如果从链表的尾部开始比较，则最后一个相同的节点就是要找的第一个公共节点，这时候可以使用栈来模拟从链表的尾部开始比较。

思路2：可以不借用辅助栈来实现，可以先计算两个链表的长度差，然后让长度更长的链表向前先走差值，然后两个链表开始比较，第一个相同的节点即是第一个公共节点。

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null){
            return null;
        }
        int length1 = getListLength(pHead1);
        int length2 = getListLength(pHead2);
        int lengthDif = length1 - length2;
        ListNode headLong = pHead1;
        ListNode headShort = pHead2;
        if(length2 > length1){
            lengthDif = length2 - length1;
            headLong = pHead2;
            headShort = pHead1;
        }
        for(int i = 0;i < lengthDif;i++){
            headLong = headLong.next;
        }
        while(headLong!=null && headShort!=null && headLong != headShort){
            headLong = headLong.next;
            headShort = headShort.next;
        }
        ListNode result = headLong;
        return result;
    }

    public int getListLength(ListNode node){
        int length = 0;
        while(node != null){
            length++;
            node = node.next;
        }
        return length;
    }
}