返回
首页
业界
电商
创业
访谈
手机
移动
报告
运营
建站
互联网+
系统
教程
搜索

C++将二叉树转为双向链表及判断两个链表是否相交

2020-01-06 14:37:49于海丽

  • 如果不带环，那么分别遍历两个链表到尾节点；
  • 若果两个链表相交，那么尾节点一定相交；
  • 如果两个链表不相交，那么尾节点一定不相交； 
    
int isJoinedNocylic(List * h1,List * h2)
{
  while(h1 != NULL)
    h1 = h1->next;
  while(h2 != NULL)
    h2 = h2->next;
   
  return h1 == h2;
}


    如果需要求出俩个链表相交的第一个节点列？

    网上看到了这样的一个解法：设置两个指针fast和slow，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则为无环链表)，这样就可以判断两个链表是否相交了，程序如下：

    
int isCycle(List * h)
{
  List * p1, * p2;
  p1 = p2 = h;
  int flag;
   
  while(p2 != NULL && p2->next != NULL)
  {
    p1 = p1->next;
    p2 = p2->next->next;
    if(p1 == p2)
    {  
      flag = 1;
      break;
    }
  }
   
  flag = 0; 
  return flag;
}

    下面看看怎么找环的入口，当fast与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：

    
2s = s + nr
s= nr

    设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。

    
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)

    (L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点（从相遇点向后遍历循环回到入口点的距离），于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇点为环入口点，也即为两个链表的第一个相同节点。程序描述如下：

相关文章 大家在看