php 排序多个有序链表 可刷新运行 刷新

原理:将其中一个链表设为起始链表,然后其它链表,与该链表进行比对。

代码:

<?php



$singleLinkedList1=new SingleLinkedList(1);
$singleLinkedList1->add(2);
$singleLinkedList1->add(7);
$singleLinkedList1->add(100);
//print_r($singleLinkedList1);


$singleLinkedList2=new SingleLinkedList(2);
$singleLinkedList2->add(4);
$singleLinkedList2->add(6);
$singleLinkedList2->add(10);
$singleLinkedList2->add(80);


$singleLinkedList3=new SingleLinkedList(3);
$singleLinkedList3->add(5);
$singleLinkedList3->add(9);
$singleLinkedList3->add(22);
$singleLinkedList3->add(28);
//print_r($singleLinkedList2);

$lists=[$singleLinkedList2,$singleLinkedList3];

print_r(sortLinkedList($lists,$singleLinkedList1));

function sortLinkedList($lists,$sortList){


    foreach ($lists as $list){
        $sortList->sortAntherList($list,$sortList->getHeader(),null);
    }

    return $sortList;

}
class Node
{
    public $val;
    public $next=null;
    public function __construct($val)
    {
        $this->val=$val;
    }

}

class SingleLinkedList
{
    private $header;

    public function __construct($val)
    {
        $this->header = new Node($val);
    }
    public function add($val) {
        $newNode = new Node($val);
        $endNode = $this->end();
        $endNode->next= $newNode;
        return true;
    }

    public function end()
    {
        $startNode=$this->header;
        while ($startNode->next!=null){
            $startNode=$startNode->next;
        }
        return $startNode;
    }
    public function shift()
    {
        $val=$this->header->val;
        if($this->header->next){
            $this->header=$this->header->next;
        }else{
            $this->setHeader(null);
        }

        return $val;
    }

    public function sortAntherList($list,$startNode,$prevNode)
    {
        $val=$list->shift();

        $newNode = new Node($val);

        while ($startNode->val<$val){
            $prevNode=$startNode;

            if(!$startNode->next){
                break;
            }
            $startNode=$startNode->next;

        }
        if(!$prevNode){//插在第一位
            $newNode->next=$startNode;
            $startNode=$newNode;
            $this->setHeader($startNode);

        }else{

            if(!$startNode->next){//最后一位

                if($startNode->val<$val){
                    $newNode->next=$list->getHeader();
                    $startNode->next=$newNode;
                    return ;
                }else{
                    $newNode->next=$startNode;
                    $prevNode->next=$newNode;
                    $startNode=$newNode;
                }


            }else{//插在中间
                $newNode->next=$startNode;
                $prevNode->next=$newNode;
                $startNode=$newNode;
            }
        }
        if(!$list->getHeader()){
            return ;
        }
        $this->sortAntherList($list,$startNode,$prevNode);
    }
    public function getHeader()
    {
        return $this->header;
    }
    public function setHeader($header)
    {
        return $this->header=$header;
    }
}

输出:

SingleLinkedList Object
(
    [header:SingleLinkedList:private] => Node Object
        (
            [val] => 1
            [next] => Node Object
                (
                    [val] => 2
                    [next] => Node Object
                        (
                            [val] => 2
                            [next] => Node Object
                                (
                                    [val] => 3
                                    [next] => Node Object
                                        (
                                            [val] => 4
                                            [next] => Node Object
                                                (
                                                    [val] => 5
                                                    [next] => Node Object
                                                        (
                                                            [val] => 6
                                                            [next] => Node Object
                                                                (
                                                                    [val] => 7
                                                                    [next] => Node Object
                                                                        (
                                                                            [val] => 9
                                                                            [next] => Node Object
                                                                                (
                                                                                    [val] => 10
                                                                                    [next] => Node Object
                                                                                        (
                                                                                            [val] => 22
                                                                                            [next] => Node Object
                                                                                                (
                                                                                                    [val] => 28
                                                                                                    [next] => Node Object
                                                                                                        (
                                                                                                            [val] => 80
                                                                                                            [next] => Node Object
                                                                                                                (
                                                                                                                    [val] => 100
                                                                                                                    [next] => 
                                                                                                                )

                                                                                                        )

                                                                                                )

                                                                                        )

                                                                                )

                                                                        )

                                                                )

                                                        )

                                                )

                                        )

                                )

                        )

                )

        )

)