PHP 反转循环双向链表

 PHP 数据结构

在使用循环双向链表时，有时需要反转它。反转列表会产生以下结果:如果给定的列表是 10->20->30->40->50，则反转列表后，列表将变为 50->40->30->20->10。

反转列表需要创建三个节点，考虑到链表不为空，分别为:tempNode指向head，prevNode指向head，curNode指向head到下一个头。然后将 prevNode 的 next 和 previous 作为其自身，使第一个节点成为反转列表的最后一个节点。之后，当curNode不是头部时调整链接（取消链接curNode并将其从前面链接到反向列表并修改curNode和prevNode 到列表中的下一个元素）。最后，将prevNode（最后一个节点）作为头。

函数reverseList就是为此目的而创建的。这是一个4步过程。

public function reverseList() {
  //1.如果 head 不为空，则创建三个节点
  // prevNode - 指向头，
  // tempNode - 指向头，
  // curNode - 指向 head 的下一个
  if($this->head != null) {
    $prevNode = $this->head;
    $tempNode = $this->head;
    $curNode = $this->head->next;
    
    //2。分配 prevNode 的下一个和上一个
    // 作为其本身，使第一个节点成为最后一个
    //反转列表的节点
    $prevNode->next = $prevNode;
    $prevNode->prev = $prevNode;
    
    while($curNode != $this->head) {
      //3。而curNode不是头部调整链接
      //（取消链接curNode并将其链接到反向列表
      //从前面开始并修改curNode和prevNode)
      $tempNode = $curNode->next;

      $curNode->next = $prevNode;
      $prevNode->prev = $curNode;
      $this->head->next = $curNode;
      $curNode->prev = $this->head;

      $prevNode = $curNode;
      $curNode = $tempNode;
    }

    //4。将 prevNode（最后一个节点）作为头
    $this->head = $prevNode;
  }
}  

下面是一个完整的程序，它使用上面讨论的概念来反转给定的循环双向链表。

<?php
//节点结构
class Node {
  public $data;
  public $next;
  public $prev;
}

class LinkedList {
  public $head;

  public function __construct(){
    $this->head = null;
  }
  
  //在列表末尾添加新元素
  public function push_back($newElement) {
    $newNode = new Node();
    $newNode->data = $newElement;
    $newNode->next = null; 
    $newNode->prev = null;
    if($this->head == null) {
      $this->head = $newNode;
      $newNode->next = $this->head;
    } else {
      $temp = new Node();
      $temp = $this->head;
      while($temp->next !== $this->head) {
        $temp = $temp->next;
      }
      $temp->next = $newNode;
      $newNode->next = $this->head;
      $newNode->prev = $temp;
      $this->head->prev = $newNode;
    }    
  }

  //反转列表
  public function reverseList() {
    if($this->head != null) {
      $prevNode = $this->head;
      $tempNode = $this->head;
      $curNode = $this->head->next;
      
      $prevNode->next = $prevNode;
      $prevNode->prev = $prevNode;
      
      while($curNode != $this->head) { 
        $tempNode = $curNode->next;

        $curNode->next = $prevNode;
        $prevNode->prev = $curNode;
        $this->head->next = $curNode;
        $curNode->prev = $this->head;

        $prevNode = $curNode;
        $curNode = $tempNode;
      }

      $this->head = $prevNode;
    }
  } 

  //显示列表内容
  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "The list contains: ";
      while(true) {
        echo $temp->data." ";
        $temp = $temp->next;
        if($temp == $this->head)
          break;        
      }
      echo "\n";
    } else {
      echo "The list is empty.\n";
    }
  }    
};

//测试代码
$MyList = new LinkedList();

//列表中添加五个元素。
$MyList->push_back(10);
$MyList->push_back(20);
$MyList->push_back(30);
$MyList->push_back(40);
$MyList->push_back(50);

//显示列表内容。
$MyList->PrintList();

//反转列表。
$MyList->reverseList();
  
//显示列表内容。
$MyList->PrintList();
?>

上面的代码将给出以下输出:

The list contains: 10 20 30 40 50 
The list contains: 50 40 30 20 10