數(shù)組

定義

數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，來存儲一組具有相同類型的數(shù)據(jù)。

關(guān)鍵點

1. 線性表
   數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)，每個數(shù)據(jù)最多只有前和后兩個方向。包含 數(shù)組、鏈表、隊列、棧等。
   非線性表：數(shù)據(jù)之間并不是簡單的前后關(guān)系。比如 二叉樹、堆、圖等。

2. 連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)
   正是因為這兩個限制，數(shù)組才有了 根據(jù)下標隨機訪問 的特性。
   但也由于這兩個限制，也讓刪除、插入數(shù)據(jù)操作變得低效，為了保證連續(xù)性，需要做大量的數(shù)據(jù)搬移工作。

時間復(fù)雜度

根據(jù)下標隨機訪問：O(1)
查找：依算法不同二不同（ 比如數(shù)組元素有序，使用二分查找，為O(logn) ）
插入：平均O(n)
刪除：平均O(n)

鏈表

不需要一塊連續(xù)的內(nèi)存空間，通過“指針”將零散的內(nèi)存塊串聯(lián)起來使用。
常見的鏈表結(jié)構(gòu)有：單鏈表、雙向鏈表、循環(huán)鏈表。

單鏈表

由許多節(jié)點串聯(lián)而成，每個節(jié)點包含數(shù)據(jù)和指向下一個節(jié)點地址的后繼指針，第一個節(jié)點叫頭節(jié)點、最后一個節(jié)點叫尾節(jié)點，尾節(jié)點的后繼指針指向一個空地址NULL，表示這是鏈表的最后一個節(jié)點。

循環(huán)鏈表

和單鏈表基本一樣，唯一區(qū)別在于循環(huán)鏈表尾節(jié)點的指針指向了頭節(jié)點。

和單鏈表相比，優(yōu)點在于從鏈尾到鏈頭比較方便。當(dāng)要處理的數(shù)據(jù)具有環(huán)形結(jié)構(gòu)特點時，就比較適合用循環(huán)鏈表。

雙向鏈表

不僅有后繼指針，還有指向前一個節(jié)點地址的前驅(qū)指針。

時間復(fù)雜度

隨機訪問：平均O(n)
插入：O(1)
刪除：O(1)

這里插入和刪除的 O(1) 是理論上的，實際情況并不是，比如下面兩個要求：
（1）刪除值等于給定值的節(jié)點
（2）刪除給定指針指向的節(jié)點
第一個得先找到節(jié)點，然后再進行刪除操作，所以時間復(fù)雜度是 O(n)。
第二個雖然不用查找了，但是必須獲得該節(jié)點的前驅(qū)節(jié)點，所以對于單鏈表還是 O(n) ，雙向鏈表就是 O(1) 了。

知識問答

1. 問：數(shù)組根據(jù)下標隨機訪問是如何實現(xiàn)的呢？
   計算機會給每個內(nèi)存單元分配一個地址，計算機通過地址來訪問內(nèi)存中的數(shù)據(jù)。當(dāng)計算機想要隨機訪問數(shù)組中的某個元素時，會先根據(jù)下面的尋址公式，計算出該元素的內(nèi)存地址，然后根據(jù)地址訪問元素。
   a[i]_address = base_address + i * data_type_size

2. 問：數(shù)組和鏈表的區(qū)別？

   • 數(shù)組的缺點就是大小固定，一經(jīng)聲明就要占用整塊的連續(xù)內(nèi)存空間，如果聲明的數(shù)組過大，可能會沒有內(nèi)存可以分配給它，導(dǎo)致內(nèi)存不足，如果聲明的數(shù)組過小，可能不夠用，需要再聲明一個更大的內(nèi)存空間，把原數(shù)組拷貝過去，比較費時；而鏈表本身沒有大小限制，天然支持動態(tài)擴容。
   • 數(shù)組支持隨機訪問，根據(jù)下標隨機訪問的時間復(fù)雜度為O(1)，插入、刪除操作的平均時間復(fù)雜度為O(n)。
   • 鏈表適合插入、刪除，時間復(fù)雜度為O(1)，隨機訪問的平均時間復(fù)雜度為O(n)。

算法編程

1. 反轉(zhuǎn)一個單鏈表。示例：

輸入: 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. 兩兩交換鏈表中的節(jié)點。
   給定一個鏈表，兩兩交換其中相鄰的節(jié)點，并返回交換后的鏈表。
   你不能只是單純的改變節(jié)點內(nèi)部的值，而是需要實際的進行節(jié)點交換。
   示例：

輸入：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. 給定一個鏈表，判斷鏈表中是否有環(huán)。
   解法思路：
   1. 不斷判斷下一個節(jié)點是否存在，如果有環(huán)，就死循環(huán)了
   2. 用一個Set記錄節(jié)點的地址，不斷判斷下一個節(jié)點的地址是否在Set中，這樣時間和空間都是 O(n)
   3. 龜兔賽跑，拿出兩個指針，一個每次走一步（慢），一個每次走兩步（快），如果有環(huán)，兩個指針肯定會相遇

答：

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;
    }
}