PHP 交换循环单链表的节点值

 PHP 数据结构

在许多情况下，在使用列表时需要交换两个节点的值。这可以通过遍历感兴趣的节点并在节点有效的情况下交换它们的值来实现。例如 - 如果给定列表是 10->20->30->40->50。交换第一个和第四个节点的值后，列表将变为 40->20->30->10->50。

函数 swapNodeValues 为此目的而创建，它是一个 4步过程.

public function swapNodeValues($node1, $node2) {
  
  //1.计算列表中的节点数
  $temp = new Node();
  $temp = $this->head;
  $N = 0;
  if ($temp != null) {
    $N++;
    $temp = $temp->next;
  }
  while($temp != $this->head) {
    $N++;
    $temp = $temp->next;
  } 

  //2。检查掉期头寸是否有效
  if($node1 < 1 || $node1 > $N || $node2 < 1 || $node2 > $N)
    return;

  //3。遍历到需要交换值的节点
  $pos1 = $this->head;
  $pos2 = $this->head;
  for($i = 1; $i < $node1; $i++) {
    $pos1 = $pos1->next;
  }
  for($i = 1; $i < $node2; $i++) {
    $pos2 = $pos2->next;
  }

  //4。交换两个节点的值
  $val = $pos1->data;
  $pos1->data = $pos2->data;
  $pos2->data = $val;
}   

下面是一个完整的程序，它使用上面讨论的概念来交换循环单链表的两个给定节点的值。

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

class LinkedList {
  public $head;

  public function __construct(){
    $this->head = null;
  }
  
  //在列表末尾添加新元素
  public function push_back($newElement) {
    $newNode = new Node();
    $newNode->data = $newElement;
    $newNode->next = 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;
    }    
  }

  //交换节点值
  public function swapNodeValues($node1, $node2) {
    
    $temp = new Node();
    $temp = $this->head;
    $N = 0;
    if ($temp != null) {
      $N++;
      $temp = $temp->next;
    }
    while($temp != $this->head) {
      $N++;
      $temp = $temp->next;
    } 

    if($node1 < 1 || $node1 > $N || $node2 < 1 || $node2 > $N)
      return;

    $pos1 = $this->head;
    $pos2 = $this->head;
    for($i = 1; $i < $node1; $i++) {
      $pos1 = $pos1->next;
    }
    for($i = 1; $i < $node2; $i++) {
      $pos2 = $pos2->next;
    }

    $val = $pos1->data;
    $pos1->data = $pos2->data;
    $pos2->data = $val;
  }   

  //显示列表内容
  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();

//交换node=1和node=4的值
$MyList->swapNodeValues(1, 4);

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

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

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