c/c++语言开发共享C语言实现单链表面试题（进阶篇）

首先给出单链表的结构，下面实现具体代码

  typedef int datatype;    typedef struct node  {      datatype data;      struct node*next;  }node,*pnode,*plist;//结点    typedef struct complexnode  {      datatype d;      struct complexnode*next;      struct complexnode*random;  }complexnode,*pcomplexnode;  

判断单链表是否带环，若带环，求环的长度，求环的入口点

判断是否带环

  pnode ifring(plist plist)//判断单链表是否带环,返回交点  {      pnode slow = plist;      pnode fast = plist;        //是否带环      while (fast&&fast->next)//注意边界问题      {          slow = slow->next;          fast = fast->next->next;          if (fast == slow)//如果相遇，则带环          {              return fast;          }      }      return null;  }  

求换的长度

  int getcirclelen(pnode meet)//求环的长度  {        pnode cur = meet;      int count = 0;      do       {          count++;          cur = cur->next;      } while (cur!=meet);      return count;  }  

求环的入口点

  pnode getcircleentry(plist plist,pnode meet)//求环的入口点  {      pnode cur = plist;      pnode fast = plist;      pnode slow = plist;      while(cur!=meet)//根据画图可分析出      {          cur  = cur->next;          meet = meet->next;      }      return cur;  }

判断两个链表是否相交，若相交，求交点。（假设链表不带环）

  pnode checkcrossnode(plist l1,plist l2)  {      pnode cur1 = l1;      pnode tail = l1;      pnode ret = null;      while(tail->next)      {          tail = tail->next;      }      tail->next = l2;      ret = ifring(l1);      return ret;  }

判断两个链表是否相交，若相交，求交点。（假设链表可能带环也可能不带环）

思想：
1. 首先应判断链表是否带环：都不带环，只有一个带环
2. 都带环：入口点在环外，入口点在环内。
所有情况如下图所示

复杂链表的复制

复杂链表的构建如上面已经给出

  complexnode crectecomplexnode(datatype d)//这里创建复杂链表的结点    {      pcomplexnode newnode = (pcomplexnode)malloc(sizeof(complexnode));      if (newnode == null)      {          perror("malloc");          return null;      }      newnode->d = d;      newnode->next = null;      newnode->random = null;      return newnode;    }  void printcomplexlist(pcomplexnode head)  {      pcomplexnode cur = head;      while(cur)      {          printf ("%d-->",cur->d);          printf ("random-->[%d]--->next",cur->random->d);          cur = cur->next;      }      printf ("n");  }    pcomplexnode clonecomplexnode(pcomplexnode head)//复制复杂链表  {      pcomplexnode cur = head;      pcomplexnode tmp = null;      pcomplexnode copy = null;      pcomplexnode tail = null;      while(cur)      {          pcomplexnode newnode = crectecomplexnode(cur->d);          tmp = cur;          cur= cur->next;          newnode->next = cur;          tmp->next = newnode;      }//复制每个节点并插入到节点后      cur = head;      while(cur)      {          cur->next->random = cur->random->next;          cur = cur->next->next;      }//调整random指针      cur = head;      copy= cur->next;      tail = copy;      while(tail->next)      {          tail->next = tail->next->next;          cur->next = tail->next;          cur = cur->next;          tail = tail->next;          cur->next = null;          return copy;      }  }    //下面给出具体的测试代码    void test3()  {      pcomplexnode pnode1 = crectecomplexnode(1);      pcomplexnode pnode2 = crectecomplexnode(2);      pcomplexnode pnode3 = crectecomplexnode(3);      pcomplexnode pnode4 = crectecomplexnode(4);      pcomplexnode pnode5 = crectecomplexnode(5);        pnode1->next = pnode2;      pnode2->next = pnode3;      pnode3->next = pnode4;        pnode1->random = pnode4;      pnode2->random = pnode1;      pnode3->random = pnode2;      pnode4->random = pnode2;      clonecomplexnode(pnode1);      printcomplexlist(pnode1);    }

这些是实现链表的面试题中较为复杂的了，链表重要的就是逻辑，把主要过程理解清楚。