分别用指针head1、head2来遍历两个链表,如果当前head1指向的数据小于head2指向的数据,则将head1指向的结点归入合并后的链表中,否则,将head2指向的结点归入合并后的链表中。如果有一个链表遍历结束,则把未结束的链表连接到合并后的链表尾部。
下图以一个简单的示例来介绍合并的具体方法。
由于链表按升序排列,首先通过比较链表第一个结点中元素的大小来确定最终合并后链表的头结点;接下来每次都找两个链表中剩余结点的最小值链接到被合并的链表后面,如上图中的虚线所示。在实现的时候需要注意,要释放head2链表的头结点,具体实现代码如下:
<?php
//链表结点
class node{
public $id;
//结点id
public $data;
//结点名称
public $next;
//下一结点
public function__construct($id,$data){
$this->id=$id;
$this->data=$data;
$this->next=null;
}
}
//单链表
class linkList{
public $header;
//链表头结点
//构造方法
public function___construct($id=null,$data=null){
$this->header=new node($id,$data,null);
}
//添加结点数据
public function addLink($node){
$current=$this->header;
while($current->next!=null){
if($current->next->id>$node->id){
break;
}
$current=$current->next;
}
$node->next=$current->next;
$current->next=$node;
}
//删除链表结点
public function free($id){
$current=$this->header;
$flag=false;
while($current->next!=null){
//echo $current->next->id."---".$id."<br>";
if($current->next->id==$id){
$flag=true;
break;
}
$current=$current->next;
}
if($flag){
$current->next=$current->next->next;
}else{
echo"未找到id=".$id."的结点!<br>";
}
}
//清空链表
public function clear(){
$this->header=null;
}
//获取链表
public function getLinkList(){
$current=$this->header;
if($current->next==null){
echo("链表为空!");
return;
}
while($current->next!=null){
echo $current->next->data." ";
if($current->next->next==null){
break;
}
$current=$current->next;
}
}
}
/*
*合并两个链表
*
*/
function Merge($head1,$head2){
if($head1==NULL)
return $head2;
if($head2==NULL)
return $head1;
$cur1=$head1->next;
//用来遍历head1
$cur2=$head2->next;
//用来遍历head2
$head=NULL;
//合并后链表的头结点
$cur=NULL;
//合并后的链表在尾结点
//合并后链表的头结点为第一个结点元素最小的那个链表的头结点
if($cur1->data>$cur2->data){
$head=$head2;
$cur=$cur2;
$cur2=$cur2->next;
}else{
$head=$head1;
$cur=$cur1;
$cur1=$cur1->next;
}
//每次找链表剩余结点的最小值对应的结点链接到合并后链表的尾部
while($cur1 && $cur2){
if($cur1->data<$cur2->data){
$cur->next=$cur1;
$cur=$cur1;
$cur1=$cur1->next;
}else{
$cur->next=$cur2;
$cur=$cur2;
$cur2=$cur2->next;
}
}
//当遍历完一个链表后把另外一个链表剩余的结点链接到合并后的链表后面
if($cur1!=NULL){
$cur->next=$cur1;
}
if($cur2!=NULL){
$cur->next=$cur2;
}
return $head;
}
$head1=new linkList();
$head2=new linkList();
$num=0;
for($i=1;$i<7;){
$head1->addLink(new node($i,$i));
$num++;
$i+=2;
}
$num=0;
for($i=2;$i<7;){
$head2->addLink(new node($num,$i));
$num++;
$i+=2;
}
echo"head1:";
$head1->getLinkList();
echo"head2:";
$head2->getLinkList();
echo"合并后的链表:";
$heads=merge($head1->header,$head2->header);
for($cur=$heads->next;$cur!=NULL;){
echo $cur->data." ";
$cur=$cur->next;
}
//释放链表所占的空间
$head1->clear();
$head2->clear();
?>
程序的运行结果为
head1:1 3 5
head2:2 4 6
合并后的链表:1 2 3 4 5 6
算法性能分析:这种方法只需要对链表进行一次遍历,因此,时间复杂度为O(n)。另外由于只需要几个指针变量来保存结点的地址信息,因此,空间复杂度为O(1)。