如何判断单链表有环 - 高飞网
363 人阅读

如何判断单链表有环

2017-07-28 02:09:46

假定有一个单向链表,如何判断它是否有环?如果有环,如何确定环的连接点在哪?如何算出环的长度?如何算出带环链表的长度?

 如何判断单向链表是否存在环?

    对于一般的单链表(无环的)来说,头指针指向头结点,其他结点除了保存数据项外,有一个指针指向下一个结点的地址。尾结点比较特殊,它没有后继结点,指向为NULL。

    而如果链表有环,尾结点不再指向NULL,而是指向链中的某个结点,如下:

思路

    目前比较常见的一种解决方法,是设计一慢一快两个指针,用指针相遇法,这里暂不介绍,先以现实中常见的一个场景来描述:

    我们上学的时候,都参加过运动会,操场一般300多米左右。在田径比赛时,有100米短跑,1000米长跑等等。    
    那么跑100米时,可以对比这里的无环链表,A、B两个运动员,在相同的起点跑到相同的终点,假设他们的速度恒定(不会一会儿慢一会快),而且A比B慢,那么,B一定先跑完,A后跑完,他们再次相遇,只有一个可能,就是在终点。



    跑1000米时,A和B一起跑,我们还是假设A和B速度恒定,A比B慢,那么如果A与B再次相遇,就不止终点一个可能了,因为B比A快,会再次超过A,下图给出了类似的跑道场景,以便读者可以理解。如果A与B一快一慢从起点开始走跑,如果相遇点不是终点(链表来说是尾结点),就说明这个链表有环。    

   

代码实现

理解了现实的场景后,看代码实现怎么做

    设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表)程序如下:

bool IsExitsLoop(slist *head)
{
    slist *slow = head, *fast = head;

    while ( fast && fast->next ) 
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }

    return !(fast == NULL || fast->next == NULL);
}

    如果是对第二个图的带环链表执行上面的操作,会得出有环,而相遇点在f。

如何找到环的入口点

    找环的入口点就有点复杂了,先说一下结论:接着上面判断是否存在环的逻辑,在相遇点之后,将slow重置到头结点重新走,fast也每次走一步,正好可以在入口点c点相遇。下面通过数学表达式进行推演:

思路

    我们先来定义一点变量:

设:

slow走的步数为:s
fast走的步数为:2s(因为fast速度是flow的两倍,路程也为两倍)
起点到入口点为:a
入口到相遇点为:x
环长的周长为:r
相遇时假设fast已经在环中转的圈数为:n
整个链表的长度为:L


如下图所示:


    推演过程:

slow:s = a +x,即slow走的路径为:起点到入口点 + 入口点到相遇点
fast:2s = a + x + nr,即fast走的路径为:起点到入口点 + 入口点到相遇点 +入口后转了n圈
由上面两个表达式得出:s = nr
由于链长为L,则L = a + r,即起点到入口点 + 环的长度
即:s = a + x = nr
     => a + x = nr = (n - 1)r  + r = (n - 1)r  +  (L -a )
     => a + x = (n -1 )r + L -a 
    当n=0时:=> a + x = L -a
    从而得出:a = L - a  -x

     现在我们来看,a为起点到入口点的距离,而L -a -x 正好也是相遇点到入口点的距离,由此,我们把slow再放到头结点位置,让它和fast一起相同速度往后走,下一次相遇时,即为入口点了。

代码实现

slist* FindLoopPort(slist *head)
{
    slist *slow = head, *fast = head;

    while ( fast && fast->next ) 
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }

    if (fast == NULL || fast->next == NULL)
        return NULL;

    slow = head;
    while (slow != fast)
    {
         slow = slow->next;
         fast = fast->next;
    }

    return slow;
}


求环的长度

    这个简单,既然环的入口点找到了,在第一次进入入口时开始计数,再次进入入口时停止计数,就是环的长度了。

求链的长度

    从头节点开始计数,第二次经过入口结点时停止计数,即为链长。

下面附上Java代码来解决链表环的问题

/**
 * 判断链表是否有环
 * 
 * @data Dec 15, 2016 9:33:26 PM
 */
public class LinkListLoop {
    public static void main(String[] args) {
        LinkList ll = new LinkList();
        ll.addNode(new Node("a", null));
        ll.addNode(new Node("b", null));
        Node nodec = new Node("c", null);
        ll.addNode(nodec);
        ll.addNode(new Node("d", null));
        ll.addNode(new Node("e", null));
        ll.addNode(new Node("f", null));
        ll.addNode(new Node("g", nodec));

        // ll.print();
        boolean isloop = ll.isloop();
        if (isloop) {
            Node enter = ll.loopPoint();// 环的入口
            System.out.println("环入口点:" + enter.value);
            int loopLen = ll.loopLen(enter);
            System.out.println("环长度:" + loopLen);
            int linkLen = ll.linkLen(enter);
            System.out.println("链长度:" + linkLen);
        }
    }
}

class LinkList {
    Node head;
    int size;

    void addNode(Node node) {
        if (head == null) {
            head = node;
        } else {
            Node node0 = head;
            while (node0.next != null) {
                node0 = node0.next;
            }
            node0.next = node;
        }
    }

    void print() {
        Node node0 = head;
        while (node0 != null) {
            System.out.print(node0.value + ",");
            node0 = node0.next;
        }
    }

    boolean isloop() {
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                System.out.println("碰撞点:" + fast.value);
                break;
            }
        }
        return fast != null && fast.next != null;
    }

    Node loopPoint() {
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
            if (slow == fast) {
                break;
            }
        }
        return slow;
    }

    /**
     * 环的长度
     * 
     * @param enter
     * @return
     */
    int loopLen(Node enter) {
        int len = 0;
        Node pNode = enter;
        while (pNode != null) {
            enter = enter.next;
            len++;
            if (pNode == enter) {
                break;
            }
        }
        return len;
    }

    /**
     * 链的长度
     * 
     * @param enter
     * @return
     */
    int linkLen(Node enter) {
        int len = 0;
        Node pNode = head;
        int count = 0;
        while (pNode != null) {
            pNode = pNode.next;
            len++;
            if (pNode == enter) {
                count++;
                if (count == 2) {
                    break;
                }
            }
        }
        return len;
    }
}

class Node {
    String value;
    Node next;

    public Node(String value, Node node) {
        this.value = value;
        this.next = node;
    }
}


参考:

https://www.douban.com/group/topic/49203127/

http://blog.csdn.net/liuxialong/article/details/6555850

http://wuchong.me/blog/2014/03/25/interview-link-questions/

http://www.cppblog.com/humanchao/archive/2008/04/17/47357.html



还没有评论!
54.91.171.137