日复一日

厚积薄发|跳跃的人生
  IT博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  25 随笔 :: 2 文章 :: 6 评论 :: 0 Trackbacks
微软面试技术题（6）
1 int  isLoop(List l) {
 2      if ( ! l)  return   - 1 ;
 3     List s  =  l.next;
 4      while (s  &&  s != l)  {
 5         s  =  s.next;
 6     }
7      if  ( ! s)  return   - 1 ;
 8      else  reutrn  1 ;
 9 }
判断一个链表是否有循环。

 1int isLoop(List l){
 2    if(!l) return 0;
 3    p=l.next;
 4    wihle(p!=l&&p!=null) {
 5        l.next=l;
 6        l=p;p=p.next;
 7    }
 8    if(p=l) return 1;
 9    return 0;
10}

实际上，在我的面试过程中，还问到了不破坏结构的其他算法。
我的答案是从链表头开始遍历，如果节点next指针指向自身，则循环存在；否则将next指针指向自身，遍历下一个节点。直至next指针为空，此时链表无循环。
posted on 2006-06-16 20:34 GwQ 阅读(157) 评论(0)  编辑 收藏 引用 所属分类: 微软面试技术题
只有注册用户登录后才能发表评论。