Java数据结构-线性表之链表应用-检测链表是否有环

àì夳堔傛蜴生んèń 2022-08-02 12:46 166阅读 0赞

如何检测一个链表是否有环？这个是一个出现频率较高的面试题。  
  如下是一个含有环的链表。  
（图片来自[http://www.nowamagic.net/librarys/veda/detail/2245][http_www.nowamagic.net_librarys_veda_detail_2245]  
一个有很多关于数据结构的文章的网站，还有其他的资料，可以看看）  
![.jpg][]

我这里解题的方法有三种：

1.  快慢指针方法：两个速度不一样的指针遍历总会相遇；
2.  利用环的顶点数和边相等的关系；
3.  两个指针遍历判断步数是否相等。

为了实现检查链表是否含有环的情况，我们需要先构建出一个含有环的链表。  
  于是乎我在之前源码的基础上增加了两个方法，代码如下：

/**
     * @TODO 设置成循环链表
     */
    public void setLoop(){
        FOLinkedNode<E> p = new FOLinkedNode<E>();
        p=this.header;
        FOLinkedNode<E> q = new FOLinkedNode<E>();
        q = this.last(p);
        q.addNext(p);
    }
    /**
     * @TODO 指定某个位置来设置链表还有环
     * @param index 链表的某个位置
     */
    public void setIndexLoop(int index){
        validateIndex(index);
        FOLinkedNode<E> p = new FOLinkedNode<E>();
        p=get(index);
        FOLinkedNode<E> q = new FOLinkedNode<E>();
        q=last(this.header);
        q.addNext(p);
    }

**1.快慢指针方法：**  
代码如下：

/**
     * @TODO 判断链表是否含有环(快慢指针法)
     * @return true or false
     */
    public boolean hasLoop(){
        FOLinkedNode<E> p = new FOLinkedNode<E>();
        FOLinkedNode<E> q = new FOLinkedNode<E>();
        p=this.header;
        if(p!=null){
            q = p.next;
            while(p!=null && q!=null && q.next!=null){
                if(p==q || p==q.next){
                    return true;
                }
                q =q.next.next;
                p = p.next;
            }
        }
        return false;
    }

快慢指针还可以用来解决“求单链表倒数第N个数”，“用标尺法快速找到单链表的中间结点”等问题。  
  可以看看“求单链表倒数第N个数”的解如下：  
[http://www.nowamagic.net/librarys/veda/detail/2243][http_www.nowamagic.net_librarys_veda_detail_2243]

**2.环的顶点数和边相等的关系。**  
  这是我想到的一种方法，由于是链表，所以我最初假设的是单链表，而我的单链表是设置了长度的，这样在进行判断是否含有环的时候可以利用长度来进行。  
  将指针是否为空和长度每次遍历减1操作来进行while循环，这样如果到长度等于0的时候而指针却不为空，此时就说明此链表含有环。这利用了环的顶点数和边相等的关系。  
代码如下：

/**
     * @TODO 利用环的顶点数和边数相等的关系进行判断是否含有环
     * @return true or false
     */
    public boolean hasLoop2(){
        FOLinkedNode<E> temp = new FOLinkedNode<E>();
        temp = this.header.next;
        int tempSize = this.size();
        while (temp != null) {
            tempSize--;
            if(tempSize<=0){
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

这个方法我其实是在打印链表的时候想到的。如果是单链表，那么打印的话只要判断指针是否为null就行；而如果是循环链表或者是含有环的链表的时候，如果要打印则会陷入死循环之中，于是乎就想到用链表的长度进行判断来打印链表。这样当需要判断链表是否含有环的时候还需要再增加一个条件，就是指针是否为空的情况，于是乎问题就有解了。

顺便贴上改进后的toString方法的代码：

@Override
    public String toString() {
        return "[" + this.NodesToString(this) + "]";
    }
    /**
     * @param foLinkedList 
     * @TODO 设置单链表的长度
     * @return 单链表的节点字符串序列
     */
    private String NodesToString(FOLinkedList<E> foll) {
        StringBuffer sb = new StringBuffer();
        if (foll.header != null) {
            sb.append(foll.header.getE());
            FOLinkedNode<E> temp = new FOLinkedNode<E>();
            temp = foll.header.next;
            int tempSize = foll.size() - 1;
            while (temp != null && tempSize!=0) {
                sb.append(", " + temp.getE());
                temp = temp.next;
                tempSize--;
            }
        }
        return sb.toString();
    }

**3.两个指针遍历判断步数是否相等**  
思路：  
  设两个工作指针p、q，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样。比如p从A走到D，用了4步，而q则用了14步。因而步数不等，出现矛盾，存在环。

这个方法相比于前面的两种方法就略次一些了，这里就没有进行代码编写了。

最后贴上测试的代码，注释的代码是测试之前的代码用的，可以忽略，也可以自行尝试。

public static void main(String[] args) {
    //      FOLinkedList<String> fol = new FOLinkedList<String>();
    //      for (int i = 1; i <= 8; i++) {
    //          fol.add("元素"+i);
    //      }
    //      fol.add("元素"+2);
    //      fol.add("元素"+7);
    //      fol.add("元素"+2);
    //      fol.add("元素"+2);
    //      fol.add("元素"+3);
    //      fol.add("元素"+11);
    //      fol.add("元素"+1);
    //      fol.add("元素"+9);
    //      System.out.println(fol);
    //      fol = FOLinkedList.removeRepeatElement(fol);
    //      System.out.println(fol);
    //      System.out.println(fol.size());
    //      fol.insert( 9,"xxx");
    //      System.out.println(fol);
    //      System.out.println(fol.size());
    //      fol.set(9,"元素9");
    //      System.out.println(fol);
    //      FOLinkedNode<String> e = fol.remove(6);
    //      System.out.println(e);
    //      System.out.println(fol);
    //      System.out.println(fol.size());
    //      FOLinkedList<String> newFol = new FOLinkedList<String>();
    //      for (int i = 1; i <= fol.size(); i++) {
    //          newFol.addFirst(fol.get(i).getE());
    //      }
    //      System.out.println(newFol);
    //      FOLinkedList<Integer> a = new FOLinkedList<Integer>();
    //      FOLinkedList<Integer> b = new FOLinkedList<Integer>();
    //      for (int i = 0,j=1; i < 10; i++,j=j+2) {
    //          a.add(j);
    //      }
    //      for (int i = 0,j=0; i < 10; i++,j=j+3) {
    //          b.add(j);
    //      }
    //      System.out.println(a);
    //      System.out.println(b);
    //      FOLinkedList<Integer> c = a.merge(b);
    //      System.out.println(c);
    
            //测试链表是否含有环
            FOLinkedList<Integer> x = new FOLinkedList<Integer>();
            for (int i = 1; i <= 10; i++) {
                x.add(i);
            }
            System.out.println(x);
            System.out.println(x.size());
            System.out.println("hasLoop2:"+x.hasLoop2());
            System.out.println("hasLoop:"+x.hasLoop());
            x.setIndexLoop(10);
            System.out.println(x);
            System.out.println(x.size());
            System.out.println("hasLoop2:"+x.hasLoop2());
            System.out.println("hasLoop:"+x.hasLoop());
        }

[http_www.nowamagic.net_librarys_veda_detail_2245]: http://www.nowamagic.net/librarys/veda/detail/2245
[.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/链表判断环.jpg
[http_www.nowamagic.net_librarys_veda_detail_2243]: http://www.nowamagic.net/librarys/veda/detail/2243