本文共 1036 字，大约阅读时间需要 3 分钟。

分析:

如果两个链表有一个公共结点,那么该公共结点之后的所有结点都是重合的,即它们的最后一个结点必然

是重合的.我们先要分别遍历两个链表得到它们的长度,并求出两个长度之差.在长的链表中先遍历长度之差个结点

之后,在同步遍历两个链表,直到找到相同的结点,或者一直到链表结束.此时,该方法的时间复杂度为O(len1+len2).

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2)	{		// 计算两个链表的表长		int len1 = GetListLength(pHead1);		int len2 = GetListLength(pHead2);		ListNode longList, shortList; // 分别指向表长较长和较短的链表		int dist = 0; // 表长之差		if (len1 > len2) // L1表长较长		{			longList = pHead1;			shortList = pHead2;			dist = len1 - len2;		}		else            // L2表长较长		{			longList = pHead2;			shortList = pHead1;			dist = len2 - len1;		}				// 表长较长的链表先遍历到第dist个结点		while (dist != 0)		{			dist--;			longList = longList.next;		}				// 同步寻找共同结点		while (longList != null)		{			if (longList == shortList) // 找到第一个公共结点			{				return longList;			}						longList = longList.next;			shortList = shortList.next;		}		return null;	}		int GetListLength(ListNode pHead)	{		int length = 0; // 链表长度默认为0		ListNode p = pHead;		while (p != null)		{			length++; // 链表长度加1			p = p.next;		}		return length;	}