题目：输入两个链表，找出它们的第一个公共结点。 假设第一个链表长度为m，第二个链表长度为n。 思路1：时间复杂度O(mn) 在第一个链表上顺序遍历每个节点，每遍历到一个节点，就在第二个链表上顺序遍历每个节点。如果在第二个链表上有一个节点和第一个链表上的节点一样，则说明两个链表在这个节点上重合，于是就找到了它们的公共节点。 思路2：时间复杂度O(m+n)，空间复杂度O(m+n) 如果两个链表有公共节点，那么公共节点出现在两个链表的尾部，如果从两个链表的尾部开始往前比较，那么最后一个相同的节点就是要找的节点。因此，分别把两个链表的节点放入两个栈里，这样两个链表的尾节点就位于两个栈的栈顶，接下来比较两个栈顶的节点是否相同，如果相同则把栈顶弹出接着比较下一个栈顶，直到找到最后一个相同的节点。 思路3：时间复杂度O(m+n) 首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。在第二次遍历时，在较长的链表上先走若干步，接着同时在两个链表上遍历，找到的第一个相同的节点就是它们的第一个公共节点。 思路3的核心代码如下：
struct ListNode{ int m_nKey; ListNode* m_pNext; }; unsigned int GetListLength(ListNode* pHead){ unsigned int length = 0; ListNode* pNode = pHead; while(pNode != nullptr){ length++; pNode = pNode->m_pNext; } return length; } ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2){ //得到两个链表的长度 unsigned int length1 = GetListLength(pHead1); unsigned int length2 = GetListLength(pHead2); int nLengthDif = length1 - length2; ListNode* pListHeadLong = pHead1; ListNode* pListHeadShort = pHead2; if(length1 < length2){ pListHeadLong = pHead2; pListHeadShort = pHead1; nLengthDif = length2 - length1; } //先在长链表上走几步，然后再同时在两个链表遍历 for(int i = 0; i < nLengthDif; i++) pListHeadLong = pListHeadLong->m_pNext; while((pListHeadLong != nullptr) && (pListHeadShort != nullptr) && (pListHeadLong != pListHeadShort)){ pListHeadLong = pListHeadLong->m_pNext; pListHeadShort = pListHeadShort->m_pNext; } //得到第一个公共节点 ListNode* pFirstCommonNode = pListHeadLong; return pFirstCommonNode; }