合并两个链表并去重(php实现)

算法 admin 248℃ 0评论

这个也是某公司面试题,自己没做出来,原因有几点:

  1. 自己学的不扎实,眼高手低
  2. 面试官要我在白板上写出程序,必须得php写,思路不行,写的时候感觉白板有点小
  3. 写的过程中发现实现还是会需要一些步骤的,而且感觉自己目前无法一步实现最优写法

所以大家还是在平时多看书,广而深,看一个东西就学会,放开手去实现,最好还是有博客记录下自己的东西,也算是对知识点的回顾,免得到时面试时被面得无(言)颜以对。

以下是PHP初步实现

<?php
/**
 * 1-2-2-3-5
 * 1-2-3-3-4-5
 *
 * 1-2-3-4-5
 */
class node{
    public $val = null;
    public $next = null;
}

class Link{
    public $head = null;
    public $test = 4;
    function __construct($arr){
        $this->head = new node();
        $p = $this->head;
        foreach($arr as $n){
            $node = new node();
            $node->val = $n;
            $p->next = $node;
            $p = $node;
        }
        $p->next = null;
    }

    function show(){
        $p = $this->head;
        while($p->next != null){
            $p = $p->next;
            echo $p->val;
        }
        echo '<br>';
    }
}

$arr1 = array(1,2,3,3,4,5);
$arr2 = array(1,2,3,4,5);
$L1 = new Link($arr1);
$L2 = new Link($arr2);

$L1->show();
$L2->show();

$L3 = new Link(array());

$p1 = $L1->head;
$p2 = $L2->head;
$p3 = $L3->head;
while(($p1->next != null) && ($p2->next != null)){
    $tp1 = $p1->next;
    $tp2 = $p2->next;
    if($tp1->val <= $tp2->val){
        if($p3->val == null || $p3->val != $tp1->val){
            $node = new node();
            $node->val = $tp1->val;
            $p3->next = $node;
            $p3 = $node;
        }
        
        $p1 = $p1->next;
    } else {  
        if($p3->val == null || $p3->val != $tp2->val){
            $node = new node();
            $node->val = $tp2->val;
            $p3->next = $node;
            $p3 = $node;
        }

        $p2 = $p2->next;
    }
}

if($p1->next != null){
    while($p1->next != null){
        if($p3->val == null || $p3->val != $tp1->val){
            $node = new node();
            $node->val = $p1->val;
            $p3->next = $node;
            $p3 = $node;
        }
        $p1 = $p1->next;
    }
}

if($p2->next != null){
    while($p2->next != null){
        if($p3->val == null || $p3->val != $tp2->val){
            $node = new node();
            $node->val = $p2->val;
            $p3->next = $node;
            $p3 = $node;
        }
        $p2 = $p2->next;
    }
}

$L3->show();

 

转载请注明:朋克网 » 合并两个链表并去重(php实现)

喜欢 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址