如何快速确认链表上是否存在环

╰+攻爆jí腚メ 2023-07-17 06:54 3阅读 0赞

> 这个问题遇到过很多次了，但是并不是说每次都很清楚。所以这次用golang的代码来实现一遍，加深理解与记忆。

如果一个链表上不存在环，那么一定能够遍历完链表中所有的Node节点；如果存在环，那么可以想象成存在一个圆形操场。在一个圆里面，如果有两个人，行走的速度不一样，那么一定会有相遇的那一刻。最佳的解法便是基于此想法，当然也有其他的解法，比如说将每个遍历的节点放进一个set里面，如果存在过，那么就存在环。

数据结构：

type Node struct {
        
    	index int
    	next *Node
    }

构建链表，随机选择是否生成环

func createNodeList() *Node{
        
    	rand.Seed(time.Now().Unix())
    	length := rand.Intn(100) + 1
    	
    	head := new(Node)
    	var tail *Node
    	
    	// 构建链表
    	for idx ,curNode := 1, head; idx <= length; idx ++ {
        
    		curNode.index = idx
    		if idx != length {
        
    			curNode.next = new(Node)
    			curNode = curNode.next
    		} else {
        
    			tail = curNode
    		}
    	}
    	
    	buildRing := rand.Intn(2)
    	if buildRing == 0 {
        
    		// 构建环
    		enterRingIndex := rand.Intn(length) + 1
    		enterRingNode := head
    		for idx:= 2; idx <= enterRingIndex; idx ++{
        
    			enterRingNode = enterRingNode.next
    		}
    		tail.next = enterRingNode
    		fmt.Println("length : ", length, ", enter ring index : ", enterRingIndex, ", Ring length : ", length - enterRingIndex + 1)
    	} else {
        
    		fmt.Println("don't build ring")
    	}
    	
    	return head
    }

输出链表，用于debug

func outputNodeList(head * Node) {
        
    	for head != nil {
        
    		fmt.Print(head.index, " ")
    		head = head.next
    	}
    }

使用两个下标，用于抽象表示圆形操场中的两个人，leader走前面，每次走两步，follower走后面，每次走一步，如果相遇，返回相遇时的Node节点。

func nodeListExistRing(head * Node) *Node {
        
    	leader, follower := head, head
    	for leader != nil && follower != nil {
        
    		leader = leader.next
    		if leader == nil {
        
    			return nil
    		}
    		leader = leader.next
    		
    		follower = follower.next
    		
    		if (leader == follower) {
        
    			return leader
    		}
    	}
    	return nil
    }

如果链表中存在环，那么环的长度就等于：follower再走一圈时走过的步长。

func calRingLength(meetNode * Node) int {
        
    	curNode := meetNode
    	curNode = curNode.next
    	count := 1
    	for ; curNode != meetNode; count ++ {
        
    		curNode = curNode.next;
    	}
    	return count
    }

如果链表存在环，那么入环点等于将leader指向head后，并以每次一步的速度往前，直到与follower再次相遇，此时的节点便是入环点。

如何证明上面的步骤是正确的？

![format_png][]

也就是说，入环时走过的路程，等于S2加上(S1+S2)的整数倍，如果leader步长变成1，并且从A点出发到达B点，那么走过的路程D，一定会等于S2+(n-1)(S1 + S2)，也就是说一定会在B点相遇。B点即入环点。

func calEnterRingIndex(meetNode * Node, head * Node) int {
        
    	var enterRingIndex = 0;
    	for head != meetNode {
        
    		head = head.next
    		meetNode = meetNode.next
    		enterRingIndex ++
    	}
    	return enterRingIndex + 1
    }

启动类，将前面过程，按照想要的逻辑拼装在一起。

func main() {
        
    	head := createNodeList()
    	meetNode := nodeListExistRing(head)
    	if meetNode == nil {
        
    		outputNodeList(head)
    	} else {
        
    		fmt.Println("RING EXIST!", ", Ring length: ", calRingLength(meetNode), ", Enter Ring Index : ", calEnterRingIndex(meetNode, head))
    	}
    }

附录：

文中公式、图及推算过程的latex源码:

\begin{tikzpicture}
        % \draw[dashed, file=blue!20]{0, 0} circle(0.5cm);
        \draw(0, 0) circle (1.5cm);
        \coordinate[label = above:$O$] (O) at (0, 0);
        \node at(0, 0)[circle,fill,inner sep=1pt]{};
    
        \coordinate[label = right:$C$] (C) at (-30:1.5);
        \node at(C)[circle,fill,inner sep=1pt]{};
    
        \coordinate[label = below right:$S_1$] (S1) at (-60:1.5);
        \coordinate[label = left:$S_2$] (S2) at (120:1.5);
    
        \coordinate[label = below: $B$] (B) at (-90:1.5);
        \node at(B)[circle,fill,inner sep=1pt]{};
    
        \coordinate[label = below: $A$] (A) at (-7, -1.5);
        \node at(A)[circle,fill,inner sep=1pt]{};
    
        \draw (A) -- (B) node[above, midway] (line) {$D$};
    \end{tikzpicture}
    
    设n为leader与follower在相遇前，比follower多走的圈数，那么便存在
    \[ 2(D + S_1) = D + S_1 + n * (S_1 + S_2) \]
    
    化简得：
    \[ 2*D + 2*S_1 = D + S_1 + n * (S_1 + S_2) \]
    \[ D + S_1 = n * (S_1 + S_2) \]
    \[ D = n * (S_1 + S_2) - S_1 \]
    \[ D = (n - 1) * (S_1 + S_2) + S_1 + S_2 - S_1 \]
    
    即：
    \[ D = (n - 1) * (S_1 + S_2) + S_2 \]

参考：https://zouyu4524.github.io/blog/tikz-plot/

[format_png]: /images/20230528/38bda3d9b27f4aff91f5afe800822341.png