主要思路为,通过调整结点指针域的指向来直接调换相邻的两个结点。如果单链表恰好有偶数个结点,那么只需要将奇偶结点对调,如果链表有奇数个结点,那么除最后一结点外的其他结点进行奇偶对调。为了便于理解,下图给出了其中第一对结点对调的方法。
在上图中,当前遍历到结点cur,通过①~⑥6个步骤用虚线的指针来代替实线的指针实现相邻结点的逆序。其中,①~④实现了前两个结点的逆序操作,⑤和⑥两个步骤向后移动指针,接着可以采用同样的方式实现后面两个相邻结点的逆序操作。
实现代码如下:
<?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 Reverse2(){
$head=$this->header;
//判断链表是否为空
if($head==NULL||$head->next==NULL)
return;
$cur=$head->next;
//当前遍历结点
$pre=$head;
//当前结点的前驱结点
$next=NULL;
//当前结点后继结点的后继结点
while($cur&&$cur->next){
$next=$cur->next->next;
//见上图第①步
$pre->next=$cur->next;
//见第②步
$cur->next->next=$cur;
//见第③步
$cur->next=$next;
//见第④步
$pre=$cur;
//见第⑤步
$cur=$next;
//见第⑥步
}
}
}
$lists=new linkList();
for($i=1;$i<8;$i++){
$lists->addLink(new node($i));
}
echo"顺序输出:";
$lists->getLinkList();
echo"<br>逆序输出:";
$lists->Reverse2();
$lists->getLinkList();
//释放链表所占的空间
$lists->clear();
?>
程序的运行结果为
顺序输出:1 2 3 4 5 6 7
逆序输出:2 1 4 3 6 5 7
上例中,由于链表有奇数个结点,因此,链表前三对结点相互交换,而最后一个结点保持在原来的位置。
算法性能分析:这种方法只需要对链表进行一次遍历,因此,时间复杂度为O(n)。另外,由于只需要几个指针变量来保存结点的地址信息,因此,空间复杂度为O(1)。