笔试算法题（27）：判断单向链表是否有环并找出环入口节点 & 判断两棵二元树是否相等...

喜欢ヅ旅行 2021-12-23 01:51 85阅读 0赞

**出题：**判断一个单向链表是否有环，如果有环则找到环入口节点；

**分析：**

*  第一个问题：使用快慢指针（fast指针一次走两步，slow指针一次走一步，并判断是否到达NULL，如果fast==slow成立，则说明链表有环）；
 *  第二个问题：fast与slow相遇时，slow一定还没有走完一圈（反证法可证明）；  
     
    
    <table> 
     <tbody> 
      <tr> 
       <td><img src="http://img3.douban.com/view/note/large/public/p201786098-1.jpg" alt=""></td> 
      </tr> 
      <tr> 
       <td align="center">&nbsp;示意图</td> 
      </tr> 
     </tbody> 
    </table>
    
      
    A为起始点，B为环入口点，C为相遇点，则a1=|AB|表示起始点到换入口的距离，a2=|CB|表示相遇点到环入口点的距离，s1=|AB|+|BC|表示slow指针走的长度，s2表示fast指针走的长度，C=|BCB|表示环的长度  
    由于fast的速度是slow的2倍，所以相遇的时候走过的长度也是2倍  
    s2=2\*s1=a1+N\*C+(s1-a1) (1)  
    N表示fast在环中走的圈数，化解(1)得到：  
    s1=N\*C (2)  
    找到a1和a2的关系：  
    a2=C-(s1-a1) (3)  
    将(2)代入(3)得到：  
    a1=a2+(N-1)\*C (4)  
    所以如果指针m从起始点A出发，指针n从相遇点C出发，n绕行(N-1)圈环之后最终跟m指针在B点相遇

**解题：**

1 struct Node {
     2         int v;
     3         Node *next;
     4 };
     5 Node* IsCycle(Node *head) {
     6         Node *fast=head, *slow=head;
     7 
     8         while(true) {
     9                 if(fast!=NULL)
    10                         fast=fast->next;
    11                 if(fast!=NULL)
    12                         fast=fast->next;
    13                 else
    14                         return NULL;
    15                 if(slow!=NULL)
    16                         slow=slow->next;
    17                 else
    18                         return NULL;
    19 
    20                 if(fast==slow)
    21                         return fast;
    22         }
    23 }
    24 Node* FindEntry(Node *head, Node *joint) {
    25         Node *m=head, *n=joint;
    26         while(true) {
    27                 if(m==n)
    28                         return m;
    29                 m=m->next;
    30                 n=n->next;
    31         }
    32 }
    33 int main() {
    34         Node* b1=new Node(); b1->v=1;
    35         Node* b2=new Node(); b2->v=2;b1->next=b2;
    36         Node* b3=new Node(); b3->v=3;b2->next=b3;
    37         Node* b4=new Node(); b4->v=4;b3->next=b4;
    38         Node* b5=new Node(); b5->v=5;b4->next=b5;
    39         Node* b6=new Node(); b6->v=6;b5->next=b6;
    40         Node* b7=new Node(); b7->v=7;b6->next=b7;
    41         Node* b8=new Node(); b8->v=8;b7->next=b8; b8->next=b3;
    42 
    43         Node* temp;
    44         if((temp=IsCycle(b1))!=NULL) {
    45                 printf("\nthe joint point is: %d",temp->v);
    46                 printf("\nthe entry of cycle is: %d",FindEntry(b1,temp)->v);
    47         }
    48         else
    49                 printf("\nthere is no cycle.");
    50         return 0;
    51 }

**出题：**判断两棵二元树是否相等（左右子树不能交叉比较）；

**分析：**使用递归实现，在树的K层，有2^K 个节点，所以会进行(2^K)\*2次调用，所以时间复杂度为O(N)；

**解题：**

1 struct Node {
     2         int value;
     3         Node *left;
     4         Node *right;
     5 };
     6 
     7 bool CompareTree(Node *first, Node *second) {
     8         if(first==NULL && second==NULL)
     9                 return true;
    10         if((first==NULL && second!=NULL) ||
    11                         (first!=NULL && second==NULL))
    12                 return false;
    13         if(first->value!=second->value)
    14                 return false;
    15         return CompareTree(first->left,second->left) &&
    16                         CompareTree(first->right, second->right);
    17 }

转载于:https://www.cnblogs.com/leo-chen-2014/p/3747122.html