关于有环单链表,即单链表中存在环路,该问题衍生出很多面试题,特在此汇总,方便查阅也帮助自己梳理下思路。

如下图1所示为有环单链表,假设头结点为H, 环的入口点为A。

有环单链表示例

关于有环单链表相关的问题:

  1. 该单链表中是否真有环存在?
  2. 如何求出环状的入口点?
  3. 如何求出环状的长度?
  4. 求解整条链表的长度?

下面我们分别针对这几个问题进行分析和解答。

判断一个单链表是否存在环

  首先,关于第一个问题,如何确定一条链表中确实存在环,关于环状的检测主要有三种方法,链表环状检测主要有三种方法:外部记录法,内部记录法以及追赶法。

  内部标记法和外部标记法其实是一个道理,不过就是辅助变量一个是在链表节点内,一个是借助辅助数组或者hash或者AVL,红黑树等 把已经访问过的节点地址存起来,每次访问下一个节点的时候进行查询看是否已经出现过。这里不再赘述。主要看追赶法,也称快满指针法,而追赶法大家一定都已经烂熟于心了。

  追赶法主要利用最大公倍数原理,用2个游标,对链表进行访问,例如:pSlow, pFast。 pSlow访问每步向前进1个节点,而pFast则每次向前前进2个节点,如果有环则pSlow和pFast必会相遇,如果pFast最终指向了NULL,则说明该链表不存在环路。因为两个指针步子迈的不一样,因为被称作快慢指针。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
    // Definition for singly - linked list.
	struct ListNode {
	    int val;
	    ListNode *next;
	    ListNode(int x) : val(x), next(nullptr) {}
	};

	bool isLoopList(ListNode *pHead){
	    if (nullptr == pHead || nullptr == pHead->next){
	        return false;
	    }

	    ListNode *pSlow = pHead;
	    ListNode *pFast = pHead;
	    while (pFast && pFast->next){
	        pFast = pFast->next->next;
	        pSlow = pSlow->next;
	
	        if (pFast == pSlow){
	            break;
	        }
	    }

	    return !(nullptr == pFast || nullptr == pFast->next);
	}

确定该有环单链表的环的入口

  关于这个问题,首先我们需要证明当pSlow和pFast第一次相遇的时候,pSlow并未走完整个链表或者恰好到达环入口点。

有环单链表

看上图(画的比较粗糙),假设 pSlow 到达环状入口点A的时候,pFast在环上某一点B,假设B逆时针方向离 A 点距离为 y ,并且整个环状的长度为R,我们知道y <= R。从A点开始,pSlow向前走y步,此时pFast从点B往前则走 2 * y 步 并与 pSlow 相遇于点 D,此时pSlow还需R - y 才能到达链表尾端,也即A点。因为y <= R,因此R - y >= 0。得证。

有环单链表

  此时我们假设相遇的时候pSlow走了s步,那pFast走2 * s步,而pFast多走的肯定是在环内绕圈,很自然我们有

  2 * s = s + n * R ; (n >= 1)

  有: s = n * R (n >= 1).

  设整个链表的长度为L, HA的长度为a ,第一次相遇点B与A的距离为x,则有

  a + x = s = n * R;

  a + x = (n - 1 + 1 ) * R = (n - 1) * R + R = (n - 1) * R + L - a;

  有 a = (n - 1) * R + (L - a - x);  有前面我们证明知,L - a - x 为我们所设变量y。 因此a = (n - 1) * R + y; (n >= 1).

  这样,我们就可以这样,相遇点设置一个指针,链表头部设置一个指针,这两个指针同时按照一步一个节点前进,第一次相遇的时候必定是相遇点指针走y + (n - 1)*R的时候,也就是入口点A的位置。得证,因此获取入口点的实现如下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
    ListNode *loopJoint(ListNode *pHead){
        if (nullptr == pHead || nullptr == pHead->next){
            return nullptr;
        }

        ListNode *pSlow = pHead;
        ListNode *pFast = pHead;
        while (pFast && pFast->next){
            pFast = pFast->next->next;
            pSlow = pSlow->next;

            if (pFast == pSlow){
                break;
            }
        }

        if (nullptr == pFast || nullptr == pFast->next){
            return nullptr;
        }

        // 此时调整两个指针为普通指针,一次一步,并且其中一个指针从头部开始,第一次相遇点一定是环的入口点
        pSlow = pHead;
        while (pFast != pSlow){
            pFast = pFast->next;
            pSlow = pSlow->next;
        }

        return pSlow;
    }

求出该有环单链表中环的长度

有了以上的基础,环状的长度就很明显了,入口点已知,沿着环状走一圈即得。

求出该有环单链表长度

同理,当R已知,而问题2中其中指向头部的指针到达环状入口点的时候HA已知,因此单链表的长度等于 L = R + a;