算法-寻找两个链表的第一个公共结点

淩亂°似流年 2022-06-09 22:37 179阅读 0赞

**题目：**  
输入两个链表，找到他们的第一个公共结点，链表结点定义如下：

struct ListNode
    {
      int value;
      ListNode *next;
    };

**解题思路：**  
首先我们需要想清楚的是，如果一个链表出现了公共结点，那么这两个链表是什么样子的，显然它的结构应该是一个“Y”型：  
![这里写图片描述][SouthEast]

由于是单向链表，所以只有一个指向下一个结点的指针。这意味着如果出现了公共结点那么这个结点之后的结点也一定是公共的，这也是为什么题目强调了**第一个**结点，也就是说永远不会有这样的情况：  
![这里写图片描述][SouthEast 1]

我当然可以通过最简单的方法实现这个任务，就是链表1走一步后遍历链表2，这样的话时间复杂度将是O(mn)，我们当然希望有一种方法可以只遍历一遍链表就找到这个结点，但是这有一个重要前提：  
**同时遍历两个链表，想要找到公共的结点就必须要在某一次循环中两个链表同时到达这个结点**，比如第一张图中的要找的结点是5，那么在某次循环中用链表2的结点4和链表1的结点5比较，那么永远不可能找到公共结点。  
所以这就需要在同时遍历前做一些准备工作，好在“Y”型的结构让这个工作变得很容易，那就是让长的链表先走几步，这个思想在[获取链表中倒数第k个结点][k]也有体现，比如链表1长度是m，链表2长度是n（m>n），公共的结点个数是k，那么链表1非公共的结点个数为m-k，链表2非公共的结点个数为n-k。那么走的步数就确定了：(m-k)-(n-k)=m-n，前提条件是先获取两个链表的长度。  
![这里写图片描述][SouthEast 2]  
在上面的图中，可以让链表1先走两步，之后链表1，2同时走，每走一步就判断一次是否为公共结点。

**代码实现：**

ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2)
    {
    
        unsigned int nLength1 = GetListLength(pHead1);
        unsigned int nLength2 = GetListLength(pHead2);
        int nLengthDif = nLength1 - nLength2;
    
        ListNode* pListHeadLong = pHead1;
        ListNode* pListHeadShort = pHead2;
        if(nLength2 > nLength1)
        {
            pListHeadLong = pHead2;
            pListHeadShort = pHead1;
            nLengthDif = nLength2 - nLength1;
        }
    
        for(int i = 0; i < nLengthDif; ++ i)
            pListHeadLong = pListHeadLong->next;
    
        while((pListHeadLong != NULL) && 
            (pListHeadShort != NULL) &&
            (pListHeadLong != pListHeadShort))
        {
            pListHeadLong = pListHeadLong->next;
            pListHeadShort = pListHeadShort->next;
        }
    
        ListNode* pFisrtCommonNode = pListHeadLong;
    
        return pFisrtCommonNode;
    }
    
    unsigned int GetListLength(ListNode* pHead)
    {
        unsigned int nLength = 0;
        ListNode* pNode = pHead;
        while(pNode != NULL)
        {
            ++ nLength;
            pNode = pNode->next;
        }
    
        return nLength;
    }

代码还是很好理解的，其中有一点是判断公共结点的条件：`pListHeadLong == pListHeadShort`，这个条件并没有对比链表结点中的value，而是直接比较的指针，如果是公共结点的话，显然两个指针指向的是同一个内存地址。

[SouthEast]: /images/20220610/915b1ef6c7664f5f87cb817e73f9e232.png
[SouthEast 1]: /images/20220610/deb81951bc194324a04d08f7b54fba40.png
[k]: http://blog.csdn.net/chaipp0607/article/details/76473464
[SouthEast 2]: /images/20220610/6c81254c284d434195adf9d7b1c8a37b.png