PHP 删除链表的奇数节点

 PHP 数据结构

删除链表的奇数节点需要遍历链表，将奇数节点一一删除。如果列表不为空，则释放该头并将下一个头作为新头。如果新头不为空，则创建两个节点 - EvenNode 和 oddNode。将 EvenNode 设置为列表的第一个偶数节点，将 oddNode 设置为列表的第二个奇数节点（原始列表中的第 3 个节点）。如果两者都不为空，则删除 oddNode 并调整链接。将两个节点移动到下一组奇偶节点。重复该过程，直到任何或两个节点都变为空。

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

复制代码复制代码public function deleteOddNodes() {
  if($this->head != null) {
    
    //1.如果 head 不为空，则将 head 的下一个设为
    //新头并删除以前的头
    $temp = $this->head;
    $this->head = $this->head->next;
    $temp = null;
    if($this->head != null) { 
      
      //2。如果新头不为空则创建
      // 节点 - EvenNode 和 oddNode
      $evenNode = $this->head;
      $oddNode = $this->head->next; 

      while($evenNode != null && $oddNode != null) {
        
        //3。而 EvenNode 和 oddNode 不为空
        // 将 EvenNode 的下一个作为 oddNode 的下一个
        // 和免费的 oddNode
        $evenNode->next = $oddNode->next;
        $oddNode = null;

        //4。并使 EvenNode 作为 EvenNode 的下一个
        $evenNode = $evenNode->next;
        
        //5。更新偶数节点和奇数节点
        if($evenNode != null)
          $oddNode = $evenNode->next;
      }
    }
  }
}      
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

下面是一个完整的程序，它使用了上面讨论的删除链表奇数节点的概念。

复制代码复制代码<?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;
    } else {
      $temp = new Node();
      $temp = $this->head;
      while($temp->next != null) {
        $temp = $temp->next;
      }
      $temp->next = $newNode;
    }    
  }

  //删除链表的奇数节点
  public function deleteOddNodes() {
    if($this->head != null) {
      $temp = $this->head;
      $this->head = $this->head->next;
      $temp = null;
      if($this->head != null) { 
        $evenNode = $this->head;
        $oddNode = $this->head->next; 
        while($evenNode != null && $oddNode != null) {
          $evenNode->next = $oddNode->next;
          $oddNode = null;
          $evenNode = $evenNode->next;
          if($evenNode != null)
            $oddNode = $evenNode->next;
        }
      }
    }
  }   

  //显示列表内容
  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "The list contains: ";
      while($temp != null) {
        echo $temp->data." ";
        $temp = $temp->next;
      }
      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->deleteOddNodes();

echo "After deleting odd nodes.\n";
//显示列表内容。
$MyList->PrintList();
?>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

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

复制代码复制代码The list contains: 10 20 30 40 50 
After deleting odd nodes.
The list contains: 20 40
1
2
3