乐趣区

关于数据结构与算法:链表学习记录

jiezi

一、什么是链表

动静的线性数据结构。

二、链表的增删改查

（一）非递归实现

<?php

class 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) 地位增加新的元素 e
public 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;
    }
}

三、递归

链表具备人造的递归性。

找到一种可视化的，可疾速失去递归后果的伎俩。

当初写累了，当前再补充这一块的内容。

退出移动版