学步园

<?php
    #合并两个非降序链表并去重,并且不能修改原链表数据
    #非降序，则链表内部有可能重复

    class Node {
        public $data = null;
        public $next = null;
    }

    function traverse($head) {
        while ($head != null) {
            echo $head->data . " ";
            $head = $head->next;
        }
    }

    #此处假设两个链表均不为空
    function merge_linkedlist($a, $b) {
        $c = new Node();
        if ($a->data < $b->data) {
            $c->data = $a->data;   
            $anext = $a->next;
            $bnext = $b;
        } else {
            $c->data = $b->data;
            $anext = $a;
            $bnext = $b->next;
        }

        $cpre = $c;

        #其实是一个添加了去重复功能的合并排序而已
        while ($anext != null && $bnext != null) {
            if ($anext < $bnext) {
                #去重复
                if ($anext->data != $cpre->data) {
                    $cnext = new Node();
                    $cnext->data = $anext->data;
                    $cpre->next = $cnext;
                    $cpre = $cnext;
                }
                $anext = $anext->next;
            } else {
                if ($bnext->data != $cpre->data) {
                    $cnext = new Node();
                    $cnext->data = $bnext->data;
                    $cpre->next = $cnext;
                    $cpre = $cnext;
                }
                $bnext = $bnext->next;
            }
        }

        while ($anext != null) {
            if ($cpre->data != $anext->data) {
                $cnext = new Node();
                $cnext->data = $anext->data;
                $cpre->next = $cnext;
                $cpre = $cnext;
            }
            $anext = $anext->next;
        }

        while ($bnext != null) {
            if ($cpre->data != $bnext->data) {
                $cnext = new Node();
                $cnext->data = $bnext->data;
                $cpre->next = $cnext;
                $cpre = $cnext;
            }
            $bnext = $bnext->next;
        }

        return $c;
    }

    $a = new Node();
    $a1 = new Node();
    $a2 = new Node();
    $a3 = new Node();
    $a4 = new Node();
    $b = new Node();
    $b1 = new Node();
    $b2 = new Node();
    $b3 = new Node();
    $b4 = new Node();
    $a->data = 0;
    $a1->data = 2;
    $a2->data = 2;
    $a3->data = 3;
    $a4->data = 4;
    $b->data = 1;
    $b1->data = 2;
    $b2->data = 2;
    $b3->data = 3;
    $b4->data = 5;
    $a->next = $a1;
    $a1->next = $a2;
    $a2->next = $a3;
    $a3->next = $a4;
    $b->next = $b1;
    $b1->next = $b2;
    $b2->next = $b3;
    $b3->next = $b4;

    $c = merge_linkedlist($a, $b);
    traverse($a);
    echo "<br>";
    traverse($b);
    echo "<br>";
    traverse($c);
?>