主要思路为,通过双重循环直接在链表上进行删除操作。外层循环用一个指针从第一个结点开始遍历整个链表,然后内层循环用另外一个指针遍历其余结点,将与外层循环遍历到的指针所指结点的数据域相同的结点删除,如下图所示。
假设外层循环从outerCur开始遍历,当内层循环指针innerCur遍历到上图点画线所框的位置(outerCur->data==innerCur->data)时,此时需要把innerCur指向的结点删除。具体步骤如下:
1)用tmp记录待删除的结点的地址。
2)为了能够在删除tmp结点后继续遍历链表中其余的结点,使innerCur指向它的后继结点,即innerCur=innerCur->next。
3)从链表中删除tmp结点。
4)释放tmp结点所占的内存空间。
实现代码如下:
<?php
header("content-type:text/html;charset=utf-8");
//链表结点
class node{
public $data;
//存储数据
public $next;
//下一结点
public function__construct($data){
$this->data=$data;
$this->next=NULL;
}
}
//单链表
class linkList{
private $header; //链表头结点
//构造方法
public function__construct($data=NULL){
$this->header=new node($data);
}
//添加结点数据
public function addLink($node){
$current=$this->header;
while($current->next!=NULL){
$current=$current->next;
}
$node->next=$current->next;
$current->next=$node;
}
//删除链表结点
public function free($data){
$current=$this->header;
$flag=false;
while($current->next!=NULL){
if($current->next->data===$data){
$flag=true;
break;
}
$current=$current->next;
}
if($flag){
$current->next=$current->next->next;
}else{
echo"未找到data=".$data."的结点!<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;
}
}
//函数功能:对带头结点的无序单链表删除重复的结点
public function removeDup(){
$head=$this->header;
if($head==NULL||$head->next=NULL)
return;
$outerCur=$head->next; //外层循环指针,指向链表第一个结点
$innerCur=NULL;
//内存循环用来遍历outerCur后面的结点
$innerPre=NULL;
//innerCur的前驱结点
$tmp=NULL;
//用来指向被删除结点的指针
for(;$outerCur!=NULL;$outerCur=$outerCur->next){
for($innerCur=$outerCur->next,$innerPre=$outerCur;$innerCur!=NULL;){
//找到重复的结点并删除
if($outerCur->data==$innerCur->data){
$tmp=$innerCur;
$innerPre->next=$innerCur->next;
$innerCur=$innerCur->next;
}else{
$innerPre=$innerCur;
$innerCur=$innerCur->next;
}
}
}
}
}
$lists=new linkList();
$lists->addLink(new node(1));
$lists->addLink(new node(3));
$lists->addLink(new node(1));
$lists->addLink(new node(5));
$lists->addLink(new node(5));
$lists->addLink(new node(7));
echo"删除重复结点前:";
$lists->getLinkList();
echo"<br>删除重复结点后:";
$lists->removeDup();
$lists->getLinkList();
//释放链表所占的空间
$lists->clear();
?>
程序的运行结果为
删除重复结点前:1 3 1 5 5 7
删除重复结点后:1 3 5 7
算法性能分析:由于这个算法采用双重循环对链表进行遍历,因此,时间复杂度为O(n
2),其中,n为链表的长度。在遍历链表的过程中,使用了常量个额外的指针变量来保存当前遍历的结点、前驱结点和被删除的结点,因此,空间复杂度为O(1)。