循环链表.md

循环链表

目录

• 知识准备
• 代码实现
• 利用循环链表解决约瑟夫环问题

循环链表是首尾相接的一种链表, 它的尾结点的后继指针指向链表的头结点.

只有头结点的循环链表

循环链表

知识准备

• 数据结构的概念和分类

代码实现

class Node
{
    public $data;
    public $next = NULL;

    public function __construct($data)
    {
        $this->data = $data;
    }
}

class CircularLinkedList
{
    // 头结点
    private $head = NULL;
    // 长度
    private $length = 0;

    // 尾部插入元素
    public function append($data)
    {
        $node = new Node($data);

        if ($this->head == NULL) {
            $this->head = $node;
        } else {
            $currNode = $this->head;

            while ($currNode->next != $this->head) {
                $currNode = $currNode->next;
            }
            $currNode->next = $node;
        }
        $this->length++;
        $node->next = $this->head;
    }

    // 遍历打印
    public function display()
    {
        echo 'LinkedList length: ' . $this->length . PHP_EOL;

        if (is_null($this->head)) {
            throw new Exception('LinkedList is NULL');
        }

        if ($this->head->next == $this->head) {
            echo $this->head->data;
            return;
        }

        $currNode = $this->head;
        while ($currNode->next != $this->head) {
            echo $currNode->data . ' ';
            $currNode = $currNode->next;
        }
        echo $currNode->data . ' ';
    }
}

// Test
$list = new CircularLinkedList();
$list->append(1);
$list->display();
$list->append(2);
$list->display();
$list->append(3);
$list->display();

执行结果

LinkedList length: 1
1
LinkedList length: 2
1 2 
LinkedList length: 3
1 2 3

利用循环链表解决约瑟夫环问题

约瑟夫环问题: n个小孩坐在一圈,每数到3就退出去,最后余下的是谁？

// 结点类
class Node
{
    public $name;
    public $next = NULL;

    public function __construct($name) {
        $this->name = $name;
    }
}

// 循环链表类
class circleList
{
    private $head = NULL;

    public function __construct($str)
    {
        $node = NULL;

        foreach (explode(" ", $str) as $k => $v) {
            if ($node) {
                $node->next = new Node($v);
                $node = $node->next;
            } else {
                $node = new Node($v);
                $this->head = $node;
            }
        }

        $node->next = $this->head;
    }

    public function find()
    {
        $currNode = $this->head;
        $count = 1;

        while ($currNode->next != $currNode) {
            if ($count % 3 == 2) {
                $currNode->next = $currNode->next->next;
            } else {
                $currNode = $currNode->next;
            }
            $count++;
        }

        echo $currNode->name;
    }
}

// Test
$str = 'aa bb cc dd ee ff gg';
$list = new circleList($str);
// dd
$list->find();