php单向链表解决约瑟夫环问题

一个经典的面试题：41一个人排成一个圈，从1开始数数，数到4，那个人就要离开队伍，然后下一个人从1开始再数，依次类推。这种算法叫做约瑟夫环问题。也可以叫丢手绢问题。由于php没有指针可以用，我们可以用类来模拟这个过程。好了，废话不多说，直接上代码：

<?php
// 节点类
class Node
{
	public $data = null;
	public $next = null;
	
	public function __construct($data)
	{
		$this->data = $data;
	}
}
// 创建节点
function createNode($node, $data)
{
	$curr = findLastNode($node);
	$newNode = new Node($data);
	$curr->next = $newNode;
}

// 计算节点的数量
function countNode($node, $head)
{
	$num = 1;
	$curr = $node;
	while(!is_null($curr->next)){
		if($curr->next == $head){
			break;
		}
		$num++;
		$curr = $curr->next;
	}

	return $num;
}

// 获取最后一个节点
function findLastNode($node)
{
	$curr = $node;
	while(!is_null($curr->next)){
		$curr = $curr->next;
	}
	
	return $curr;
}

// 删除节点 $no -- 指定删除的节点位置
function delNode(&$node, $no)
{
	$curr = $node;
	$num = 1;
	while(($num + 1) < $no ){
		$curr = $curr->next;
		$num++;
	}
	
	$curr->next = $curr->next->next;
	return $curr->next;
}

// 展示节点数据
function showNode($node, $head)
{
	$curr = $node;
	while(!is_null($curr->next)){
		echo $curr->data . "号<br/>";
		if($curr->next == $head){
			break;
		}
		$curr = $curr->next;
	}
}

// 头结点
$head = new Node(1);

// 41 个人
for($i = 2; $i < 42; $i++){
	
	createNode($head, $i);
}

// 排成一圈
$last = findLastNode($head);
$last->next = $head;

// 每数到4 退出一个
$count = countNode($head, $head);
while($count > 3){
	
	$head = delNode($head, 4);
	$count = countNode($head, $head);
}

echo "41个人从 1-41编号，每数到4退出一个人，最后剩下的是：<br/>";
showNode($head, $head);