一、什么是链表
动静的线性数据结构。
二、链表的增删改查
（一）非递归实现
<?phpclass LinkedList{ // protected Node $head; protected Node $dummyHead; // 虚构头结点 private $size; public function __construct() { // $this->head = null; $this->dummyHead = new Node(); $this->size = 0; } public function getSize(): int { return $this->size; } public function isEmpty(): bool { return $this->size == 0; } // 在链表头增加新的元素 public function addFirst($e) { $this->add(0, $e); } // 在链表的 index (0-based) 地位增加新的元素 e public function add($index, $e) { // 判断 index 的合法性 if ($index < 0 || $index > $this->size) { // 留神 index 能够取到 size 的，因为能够在最初一个节点增加元素 throw new \Exception('Add failed. illegal index'); } $prev = $this->dummyHead; for ($i = 0; $i < $index; $i++) { $prev = $prev->next; } // 程序很重要 $node = new Node($e); $node->next = $prev->next; $prev->next = $node; // 更优雅的写法 // $prev->next = new Node($e, $prev->next); $this->size ++; } // 在链表开端增加元素 e public function addLast($e) { $this->add($this->size, $e); } // 取得链表中第 index 个地位的元素： public function get($index) { if ($index < 0 && $index >= $this->size) { throw new \Exception('Get failed, Illeal index'); } $cur = $this->dummyHead->next; for ($i = 0; $i < $index; $i++) { $cur = $cur->next; } return $cur->e; } // 取得链表的第一个元素 public function getFrist() { return $this->get(0); } // 取得链表的最初一个元素 public function getLast() { return $this->get($this->size - 1); } // 批改链表的第 index 个地位的元素 public function set($index, $e) { if ($index < 0 && $index >= $this->size) { throw new \Exception('Set failed, Illeal index'); } $cur = $this->dummyHead->next; for ($i = 0; $i < $index; $i++) { $cur = $cur->next; } $cur->e = $e; } // 查找链表中是否存在元素 e public function contains($e) { $cur = $this->dummyHead->next; while ($cur != null) { if ($e == $cur->e) { return true; } $cur = $cur->next; } return false; } // 从链表中删除第 index 个元素，并返回删除元素的值 public function remove($index) { if ($index < 0 || $index >= $this->size) { throw new \Exception('Delete failed, illegal index'); } $prev = $this->dummyHead; for ($i = 0; $i < $index; $i++) { $prev = $prev->next; } $retNode = $prev->next; $prev->next = $retNode->next; $retNode->next = NULL; $this->size--; return $retNode->e; } // 从链表中删除第一个元素，返回删除元素 public function removeFirst() { return $this->remove(0); } // 从链表中删除最初一个元素，返回删除元素 public function removeLast() { return $this->remove($this->size - 1); } public function toString() { $cur = $this->dummyHead->next; $ret = ''; while ($cur != null) { $ret .= $cur->e . '->'; $cur = $cur->next; } $ret .= 'NULL'; return $ret; }}class Node{ public $e; public $next; public function __construct($e = null, $next = null) { $this->e = $e; $this->next = $next; }}1. 虚构头结点（dummy head）
为什么要应用虚构头结点？详情参考 链表问题：虚构节点dummy
因为头结点的上一个节点不存在，很多对于其余节点，须要用上上一个节点的操作对头结点就不适宜，因而，就须要独自思考头结点。
虚构头结点的目标就是打消头结点的特殊性，把头结点当做一个一般的节点来解决。即在头结点的后面加上了一个虚构头结点。
2. 增删
在链表两头增加和删除元素的要害：找到要增加或删除的节点的前一个节点。
减少元素示意图：
删除元素示意图：
这也是用虚构头结点的起因：如果想要在头结点减少一个元素或者删除头结点，那么就须要找到头结点的前一个节点，然而头结点后面是没有节点的，比拟常见的做法是分状况探讨；更好的做法是应用虚构头结点这种技巧，把头结点也当做一般元素来解决，最终也不会对后果产生影响，防止了分类探讨。
值得一提的是，在减少或删除元素时遍历链表时，是从虚构头结点开始遍历的，而非链表的第一个元素开始，代码如下：
// 在链表的 index (0-based) 地位增加新的元素 epublic function add($index, $e){ ... // 从 dummyHead 开始遍历 $prev = $this->dummyHead; for ($i = 0; $i < $index; $i++) { $prev = $prev->next; } $node = new Node($e); $node->next = $prev->next; $prev->next = $node; $this->size ++;}// 从链表中删除第 index 个元素，并返回删除元素的值public function remove($index){ ... // 从 dummyHead 开始遍历 $prev = $this->dummyHead; for ($i = 0; $i < $index; $i++) { $prev = $prev->next; } $retNode = $prev->next; $prev->next = $retNode->next; $retNode->next = NULL; $this->size--; return $retNode->e;}为什么要从 dummyHead 开始遍历呢？就不得不再提一遍减少或者删除元素的重点了：找到要增加或删除的节点的前一个节点，即咱们要找到的前一个节点而非指标节点。
举个例子，在链表 L 中地位为 2 的中央增加一个节点 6，链表 L 如下：
| index | 0 | 1 | 2 | 3 | 4 | 5 | next |
|---|---|---|---|---|---|---|---|
| val | 1 | 2 | 3 | 4 | 5 | 6 | null |
当初在头结点后面加上一个虚构头结点：
| index | dummyHead | 0 | 1 | 2 | 3 | 4 | 5 | next |
|---|---|---|---|---|---|---|---|---|
| val | null | 1 | 2 | 3 | 4 | 5 | 6 | null |
遍历的指标节点是 L[1]。
dummyHead -> next = L[0]L[0] -> next = L[1]两次就找到了指标节点的前一个节点，和待增加的地位 2 对立。
3. 改查
遍历找到指标节点即可。然而与增删有些许不同，改查并不是从 dummyHead 开始遍历，而是从链表的头结点开始。
举个例子，获取 L 中索引为 2 的元素的值，L 链表如下：
| index | 0 | 1 | 2 | 3 | 4 | 5 | next |
|---|---|---|---|---|---|---|---|
| val | 1 | 2 | 3 | 4 | 5 | 6 | null |
如果从 dummyHead 开始遍历，循环两次，找到的是 L[1] 这个元素，那么如果是从头结点开始遍历，那么遍历两次就能够找到指标元素了。
L[0] -> next = L[1];L[1] -> next = L[2];查和改的代码如下：
// 批改链表的第 index 个地位的元素public function set($index, $e){ ... // 从头结点开始遍历 $cur = $this->dummyHead->next; for ($i = 0; $i < $index; $i++) { $cur = $cur->next; } $cur->e = $e;}// 取得链表中第 index 个地位的元素：public function get($index){ ... // 从头结点开始遍历 $cur = $this->dummyHead->next; for ($i = 0; $i < $index; $i++) { $cur = $cur->next; } return $cur->e;}三、翻转链表
- 援用
- 指针
- 递归
第一版：
public function reverseList($head) { if ($head->next == null) { return $head; } $reversedList = $this->reverseList($head->next); $head->next = null; $tail = $reversedList; while ($tail->next != null) { $tail = $tail->next; } $tail->next = $head; return $reversedList; }改良：
<?php/** * Definition for a singly-linked list. * class ListNode { * public $val = 0; * public $next = null; * function __construct($val) { $this->val = $val; } * } */class Solution { /** * @param ListNode $head * @return ListNode */ function reverseList($head) { if ($head->next == null) { return $head; } $reversedList = $this->reverseList($head->next); $head->next->next = $head; $head->next = null; return $reversedList; }}三、递归
链表具备人造的递归性。
找到一种可视化的，可疾速失去递归后果的伎俩。
当初写累了，当前再补充这一块的内容。