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

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

最后看到了别人的代码,总结如下:

head指针指向链表表头,index指针指向链表尾节点。

所有节点的左指针都指向前一节点,右指针都指向后一节点。

因此:(中间过程)

  • 当前节点的左指针指向表尾节点;
  • 表尾节点的右指针指向当前节点;
  • 更新,尾节点指向当前节点;

    (对于表头,即尾节点指向NULL),初始化Head节点。

    代码如下:

    
    void convertToDoubleList(BSTreeNode* pCurrent)
    {
      pCurrent->m_pLeft=pIndex;
      if (pIndex == NULL)
      {
        pHead=pCurrent;
      }
      else
      {
        pIndex->m_pRight=pCurrent;
      }
      pIndex=pCurrent;
    }
    
    


    判断俩个链表是否相交

    给出俩个单向链表的头指针,比如 h1,h2,判断这俩个链表是否相交。

    为了简化问题,我们假设俩个链表均不带环。

    问题扩展:

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

    链表定义

    
    typedef struct node
    {
      int data;
      struct node * next;
    }List;