数组

定义

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

关键点

1. 线性表
   数据排成像一条线一样的结构，每个数据最多只有前和后两个方向。包含 数组、链表、队列、栈等。
   非线性表：数据之间并不是简单的前后关系。比如 二叉树、堆、图等。

2. 连续的内存空间和相同类型的数据
   正是因为这两个限制，数组才有了 根据下标随机访问 的特性。
   但也由于这两个限制，也让删除、插入数据操作变得低效，为了保证连续性，需要做大量的数据搬移工作。

时间复杂度

根据下标随机访问：O(1)
查找：依算法不同二不同（ 比如数组元素有序，使用二分查找，为O(logn) ）
插入：平均O(n)
删除：平均O(n)

链表

不需要一块连续的内存空间，通过“指针”将零散的内存块串联起来使用。
常见的链表结构有：单链表、双向链表、循环链表。

单链表

由许多节点串联而成，每个节点包含数据和指向下一个节点地址的后继指针，第一个节点叫头节点、最后一个节点叫尾节点，尾节点的后继指针指向一个空地址NULL，表示这是链表的最后一个节点。

循环链表

和单链表基本一样，唯一区别在于循环链表尾节点的指针指向了头节点。

和单链表相比，优点在于从链尾到链头比较方便。当要处理的数据具有环形结构特点时，就比较适合用循环链表。

双向链表

不仅有后继指针，还有指向前一个节点地址的前驱指针。

时间复杂度

随机访问：平均O(n)
插入：O(1)
删除：O(1)

这里插入和删除的 O(1) 是理论上的，实际情况并不是，比如下面两个要求：
（1）删除值等于给定值的节点
（2）删除给定指针指向的节点
第一个得先找到节点，然后再进行删除操作，所以时间复杂度是 O(n)。
第二个虽然不用查找了，但是必须获得该节点的前驱节点，所以对于单链表还是 O(n) ，双向链表就是 O(1) 了。

知识问答

1. 问：数组根据下标随机访问是如何实现的呢？
   计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机想要随机访问数组中的某个元素时，会先根据下面的寻址公式，计算出该元素的内存地址，然后根据地址访问元素。
   a[i]_address = base_address + i * data_type_size

2. 问：数组和链表的区别？

   • 数组的缺点就是大小固定，一经声明就要占用整块的连续内存空间，如果声明的数组过大，可能会没有内存可以分配给它，导致内存不足，如果声明的数组过小，可能不够用，需要再声明一个更大的内存空间，把原数组拷贝过去，比较费时；而链表本身没有大小限制，天然支持动态扩容。
   • 数组支持随机访问，根据下标随机访问的时间复杂度为O(1)，插入、删除操作的平均时间复杂度为O(n)。
   • 链表适合插入、删除，时间复杂度为O(1)，随机访问的平均时间复杂度为O(n)。

算法编程

1. 反转一个单链表。示例：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

答：

class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function reverseList($head) {
        $cur = $head;
        $prev = null;
        while ($cur) {
            $nextTmp = $cur->next;
            $cur->next = $prev;
            $prev = $cur;
            $cur = $nextTmp;
        }
        return $prev;
    }
}

2. 两两交换链表中的节点。
   给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
   你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
   示例：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

答：

class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function swapPairs($head) {
        $newHead = new ListNode();
        $pre = $newHead;
        $pre->next = $head;

        while ($pre->next && $pre->next->next) {
            $a = $pre->next;
            $b = $a->next;

            $a->next = $b->next;
            $b->next = $a;
            $pre->next = $b;

            $pre = $a;
        }

        return $newHead->next;
    }
}

3. 给定一个链表，判断链表中是否有环。
   解法思路：
   1. 不断判断下一个节点是否存在，如果有环，就死循环了
   2. 用一个Set记录节点的地址，不断判断下一个节点的地址是否在Set中，这样时间和空间都是 O(n)
   3. 龟兔赛跑，拿出两个指针，一个每次走一步（慢），一个每次走两步（快），如果有环，两个指针肯定会相遇

答：

class Solution {
    /**
     * @param ListNode $head
     * @return Boolean
     */
    function hasCycle($head) {
        $slow = $fast = $head;
        while ($slow && $fast && $fast->next) {
            $slow = $slow->next;
            $fast = $fast->next->next;
            if ($slow == $fast) {
                return true;
            }
        }
        return false;
    }
}