链表问题_两个链表的第一个公共节点

喜欢ヅ旅行 2022-05-21 04:17 131阅读 0赞

题目：输入两个链表，找出它们的第一个公共结点  
分析：对于这个问题有三种思路：  
1、蛮力算法，当遍历到一个节点时，就在另外一个链表上顺序遍历，并且判断是否相等，如果想等就是第一个重合的节点，对于两个长度分别为m和n的链表，所需要的时间为O(m\*n)。实现如下：

struct ListNode {
           int val;
            struct ListNode *next;
            ListNode(int x) :
                  val(x), next(NULL) {
            }
      };
      /*蛮力解法*/
      ListNode* FindFirstCommonNode(ListNode* phead1, ListNode* phead2)
      {
          ListNode*pnode1 = phead1;
          while (pnode1)
          {
            ListNode*pnode2 = phead2;
            if (!pnode2)
            {
                return NULL;
            }
            while (pnode2)
            {
                if (pnode2 == pnode1)
                    return pnode1;
                pnode2 = pnode2->next;
            }
            pnode1 = pnode1->next;
        }
          return NULL;
      }

2、由于两个链表有公共节点，则在第一个公共节点之后，所有的节点都是重合的，所以可以倒着判断，每次判断两个节点是否想等，当遇到第一个不等的节点时，就可以得到该结点的next就为这两个链表的第一个公共节点，这里为了从末尾到头开始访问借助栈结构，相当于花费O(m+n)的空间，是用空间来换时间的方法，实现如下：

ListNode* FindFirstCommonNode(ListNode* phead1, ListNode* phead2)
      {
          stack<ListNode*> node1;
          stack<ListNode*> node2;
          ListNode*pnode1 = phead1;
          ListNode*pnode2 = phead2;
    
          while (pnode1)
          {
              node1.push(pnode1);
              pnode1 = pnode1->next;
          }
    
          while (pnode2)
          {
              node2.push(pnode2);
              pnode2 = pnode2->next;
          }
          while (node1.size() > 0 && node2.size() > 0)
          {
              if (node1.top() == node2.top())
              {
                  node1.pop();
                  node2.pop();
              }
              else
                  return node1.top()->next;
          }
    
          return NULL;
      }

3、当两个长度想等时，可以很自然的想到，可以通过同时在两个链表上遍历，当遇到第一个相等的节点就是第一个公共节点，借助于这种想法，当两个链表长度不相等时，我们可以先算出两个链表的长度差diff，让指针先在长的链表上走diff步，然后这两个指针同时开始走就可以解决长短不同的情况，这样再不用辅助空间的情况下，时间效率可以达到O(m+n)。具体的实现如下：

//O(n)，不需要辅助空间
      ListNode* FindFirstCommonNode(ListNode* phead1, ListNode* phead2)
      {
          int length1 = 0;
          int length2 = 0;
          int diff = 0;
          ListNode* pnode_short = phead1;
          ListNode* pnode_long = phead2;
    
          while (pnode_short)
          {
              ++length1;
              pnode_short = pnode_short->next;
          }
    
          while (pnode_long)
          {
              ++length2;
              pnode_long = pnode_long->next;
          }
    
          diff = length2 - length1;
          pnode_short = phead1;
          pnode_long = phead2;
    
          if (length2 < length1)
          {
              diff = length1 - length2;
              pnode_short = phead2;
              pnode_long = phead1;
          }
    
          for (int i = 0; i < diff; i++)
          {
              pnode_long = pnode_long->next;
          }
    
          while (pnode_long&&pnode_short)
          {
              if (pnode_long == pnode_short)
                  return pnode_long;
              pnode_long = pnode_long->next;
              pnode_short = pnode_short->next;
          }
          return NULL;
      }