算法模塊

1. 鏈表

1. 鏈表翻轉(zhuǎn)

// 遞歸
ListNode* reverseList(ListNode* head)
{
    if(NULL == head || NULL == head->next)
        return head;
    ListNode * p = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;

    return p;
}
// 非遞歸
ListNode* reverseList(ListNode* head) {
    ListNode *curr = head;
    if (curr == NULL) {
        return NULL;
    }

    ListNode *prev = NULL, *temp = NULL;
    while (curr != NULL) {
        temp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = temp;
    }

    return prev;
}

2. 單鏈表判斷是不是環(huán)+求環(huán)位置+求環(huán)長(zhǎng)度

bool hasCycle(ListNode *head) {
    if (head == nullptr) {
        return false;
    }
    ListNode *fast,*slow;
    slow = head;
    fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

以圖片為例，假設(shè)環(huán)入口距離鏈表頭的長(zhǎng)度為L(zhǎng)，快慢指針相遇的位置為cross
，且該位置距離環(huán)入口的長(zhǎng)度為S。考慮快慢指針移動(dòng)的距離，慢指針走了L+S
，快指針走了L+S+nR
(這是假設(shè)相遇之前快指針已經(jīng)繞環(huán)n圈)。由于快指針的速度是慢指針的兩倍，相同時(shí)間下快指針走過(guò)的路程就是慢指針的兩倍，所以有2(L+S)=L+S+nR
，化簡(jiǎn)得L+S=nR

當(dāng)n=1時(shí)，即快指針在相遇之前多走了一圈，即L+S=R，也就是L=R?S，觀察片表示從鏈表頭到環(huán)入口的距離，而R?S表示從cross繼續(xù)移動(dòng)到環(huán)入口的距離，既然二者是相等的，那么如果采用兩個(gè)指針，一個(gè)從表頭出發(fā)，一個(gè)從cross出發(fā)，那么它們將同時(shí)到達(dá)環(huán)入口。即二者相等時(shí)便是環(huán)入口節(jié)點(diǎn)
當(dāng)n>1時(shí)，上式為L(zhǎng)=nR?S，L仍然表示從鏈表頭到達(dá)環(huán)入口的距離，而nR?S可以從cross出發(fā)移動(dòng)nR步后再倒退S步，從cross移動(dòng)nR步后回到cross位置，倒退S
步后是環(huán)入口，所以也是同時(shí)到達(dá)環(huán)入口。即二者相等時(shí)便是環(huán)入口節(jié)點(diǎn)
所以尋找環(huán)入口的方法就是采用兩個(gè)指針，一個(gè)從表頭出發(fā)，一個(gè)從相遇點(diǎn)出發(fā)，一次都只移動(dòng)一步，當(dāng)二者相等時(shí)便是環(huán)入口的位置.

ListNode *detectCycle(ListNode *head) {
    if (head == nullptr) {
        return nullptr;
    }
    ListNode *fast,*slow;
    slow = head;
    fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            ListNode *slow2 = head;
            while (slow2 != slow) {
                slow = slow->next;
                slow2 = slow2->next;
            }
            return slow2;
        }
    }
    return nullptr;
}

3. 兩個(gè)鏈表相交 求交點(diǎn)

兩個(gè)鏈表，從某個(gè)節(jié)點(diǎn)開(kāi)始相交，找到相交節(jié)點(diǎn)
方法很多，簡(jiǎn)單列舉一下
將其中一個(gè)鏈表的頭尾相連，問(wèn)題轉(zhuǎn)化為求環(huán)入口節(jié)點(diǎn)
用兩個(gè)棧分別記錄兩個(gè)鏈表的節(jié)點(diǎn)，再?gòu)棾?，找到最后一個(gè)相等的節(jié)點(diǎn)
一個(gè)容易想到的方法是，先得到兩個(gè)鏈表的長(zhǎng)度，然后得到長(zhǎng)度的差值 distance，兩個(gè)指針?lè)謩e從兩個(gè)鏈表頭部遍歷，其中較長(zhǎng)鏈表指針先走 distance 步，然后同時(shí)向后走，當(dāng)兩個(gè)指針相遇的時(shí)候，即鏈表的交點(diǎn)

int getListLength(ListNode *head) {
    if (head == nullptr) {
        return 0;
    }
    int length = 0;
    ListNode *p = head;
    while (p!=nullptr) {
        p = p->next;
        length ++;
    }
    return length;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lengthA = getListLength(headA);
    int lengthB = getListLength(headB);

    if (lengthA > lengthB) {
        std::swap(headA, headB);
    };
    int distance = abs(lengthB - lengthA);
    ListNode *p1 = headA;
    ListNode *p2 = headB;
    while(distance--) {
        p2 = p2->next;
    }
    while (p1 != nullptr && p2 != nullptr) {
        if (p1 == p2)
            return p1;
        p1 = p1->next;
        p2 = p2->next;
    }
    return NULL;
}

4. 單鏈表找中間節(jié)點(diǎn)

用快慢指針?lè)?，?dāng)快指針走到鏈表結(jié)尾時(shí)，慢指針剛好走到鏈表的中間

ListNode* middleNode(ListNode* head) {
    ListNode *slow = head;
    ListNode *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

5. 單鏈表合并

兩個(gè)鏈表本身都是排序過(guò)的，把兩個(gè)鏈表從頭節(jié)點(diǎn)開(kāi)始，逐個(gè)節(jié)點(diǎn)開(kāi)始進(jìn)行比較，最后剩下的節(jié)點(diǎn)接到尾部

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    if (l1 == nullptr) {
        return l2;
    }
    if (l2 == nullptr) {
        return l1;
    }
    ListNode dummy(-1);
    ListNode *p = &dummy;
    for (; l1 && l2; p = p->next) {
        if (l1->val < l2->val) {
            p->next = l1;
            l1 = l1->next;
        } else {
            p->next = l2;
            l2 = l2->next;
        }
    }
    p->next = l1 != nullptr ? l1 : l2;
    return dummy.next;
}

2. 樹(shù)

二叉樹(shù)

：二叉樹(shù)是有限個(gè)結(jié)點(diǎn)的集合，這個(gè)集合或者是空集，或者是由一個(gè)根結(jié)點(diǎn)和兩株互不相交的二叉樹(shù)組成，其中一株叫根的做左子樹(shù)，另一棵叫做根的右子樹(shù)。
二叉樹(shù)的性質(zhì)：
性質(zhì)1：在二叉樹(shù)中第 i 層的結(jié)點(diǎn)數(shù)最多為2^(i-1)（i ≥ 1）
性質(zhì)2：高度為k的二叉樹(shù)其結(jié)點(diǎn)總數(shù)最多為2^k－1（ k ≥ 1）
性質(zhì)3：對(duì)任意的非空二叉樹(shù) T ，如果葉結(jié)點(diǎn)的個(gè)數(shù)為 n0，而其度為 2 的結(jié)點(diǎn)數(shù)為 n2，則：n0 = n2 + 1
滿(mǎn)二叉樹(shù)：深度為k且有2^k －1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)
完全二叉樹(shù)：深度為 k 的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)都與深度為 k 的滿(mǎn)二叉樹(shù)中編號(hào)從 1 至 n 的結(jié)點(diǎn)一一對(duì)應(yīng)，稱(chēng)之為完全二叉樹(shù)。（除最后一層外，每一層上的節(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)）
性質(zhì)4：具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2n + 1
注意：僅有前序和后序遍歷，不能確定一個(gè)二叉樹(shù)，必須有中序遍歷的結(jié)果

堆

如果一棵完全二叉樹(shù)的任意一個(gè)非終端結(jié)點(diǎn)的元素都不小于其左兒子結(jié)點(diǎn)和右兒子結(jié)點(diǎn)（如果有的話(huà)） 的元素，則稱(chēng)此完全二叉樹(shù)為最大堆。
同樣，如果一棵完全二叉樹(shù)的任意一個(gè)非終端結(jié)點(diǎn)的元素都不大于其左兒子結(jié)點(diǎn)和右兒子結(jié)點(diǎn)（如果 有的話(huà)）的元素，則稱(chēng)此完全二叉樹(shù)為最小堆。
最大堆的根結(jié)點(diǎn)中的元素在整個(gè)堆中是最大的；
最小堆的根結(jié)點(diǎn)中的元素在整個(gè)堆中是最小的。

哈弗曼樹(shù)

定義：給定n個(gè)權(quán)值作為n的葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱(chēng)這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)為哈夫曼樹(shù)(Huffman tree)。
構(gòu)造：假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為 w1、w2、…、wn，則哈夫曼樹(shù)的構(gòu)造規(guī)則為：將w1、w2、…，wn看成是有 n 棵樹(shù)的森林(每棵樹(shù)僅有一個(gè)結(jié)點(diǎn))；
在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和；
從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林；
重復(fù)(2)、(3)步，直到森林中只剩一棵樹(shù)為止，該樹(shù)即為所求得的哈夫曼樹(shù)。

二叉排序樹(shù)

二叉排序樹(shù)（Binary Sort Tree）又稱(chēng)二叉查找樹(shù)（Binary Search Tree），亦稱(chēng)二叉搜索樹(shù)。
二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：
若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；
左、右子樹(shù)也分別為二叉排序樹(shù)；
沒(méi)有鍵值相等的節(jié)點(diǎn)
二分查找的時(shí)間復(fù)雜度是O(log(n))，最壞情況下的時(shí)間復(fù)雜度是O(n)（相當(dāng)于順序查找）

B-樹(shù)

B-樹(shù)：B-樹(shù)是一種非二叉的查找樹(shù)， 除了要滿(mǎn)足查找樹(shù)的特性，還要滿(mǎn)足以下結(jié)構(gòu)特性：
一棵 m 階的B-樹(shù)：
樹(shù)的根或者是一片葉子(一個(gè)節(jié)點(diǎn)的樹(shù)),或者其兒子數(shù)在 2 和 m 之間。
除根外，所有的非葉子結(jié)點(diǎn)的孩子數(shù)在 m/2 和 m 之間。
所有的葉子結(jié)點(diǎn)都在相同的深度。
B-樹(shù)的平均深度為logm/2(N)。執(zhí)行查找的平均時(shí)間為O(logm)；

Trie 樹(shù)

Trie 樹(shù)，又稱(chēng)前綴樹(shù)，字典樹(shù)， 是一種有序樹(shù)，用于保存關(guān)聯(lián)數(shù)組，其中的鍵通常是字符串。與二叉查找樹(shù)不同，鍵不是直接保存在節(jié)點(diǎn)中，而是由節(jié)點(diǎn)在樹(shù)中的位置決定。一個(gè)節(jié)點(diǎn)的所有子孫都有相同的前綴，也就是這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的字符串，而根節(jié)點(diǎn)對(duì)應(yīng)空字符串。一般情況下，不是所有的節(jié)點(diǎn)都有對(duì)應(yīng)的值，只有葉子節(jié)點(diǎn)和部分內(nèi)部節(jié)點(diǎn)所對(duì)應(yīng)的鍵才有相關(guān)的值。
Trie 樹(shù)查詢(xún)和插入時(shí)間復(fù)雜度都是 O(n)，是一種以空間換時(shí)間的方法。當(dāng)節(jié)點(diǎn)樹(shù)較多的時(shí)候，Trie 樹(shù)占用的內(nèi)存會(huì)很大。
Trie 樹(shù)常用于搜索提示。如當(dāng)輸入一個(gè)網(wǎng)址，可以自動(dòng)搜索出可能的選擇。當(dāng)沒(méi)有完全匹配的搜索結(jié)果，可以返回前綴最相似的可能。

二叉樹(shù)遍歷算法
二叉樹(shù)是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，很多其它數(shù)據(jù)結(jié)構(gòu)都是基于二叉樹(shù)的基礎(chǔ)演變而來(lái)的。對(duì)于二叉樹(shù)，有深度遍歷和廣度遍歷，深度遍歷有前序、中序以及后序三種遍歷方法，廣度遍歷即我們平常所說(shuō)的層次遍歷。因?yàn)闃?shù)的定義本身就是遞歸定義，因此采用遞歸的方法去實(shí)現(xiàn)樹(shù)的三種遍歷不僅容易理解而且代碼很簡(jiǎn)潔，而對(duì)于廣度遍歷來(lái)說(shuō)，需要其他數(shù)據(jù)結(jié)構(gòu)的支撐，比如堆了。所以，對(duì)于一段代碼來(lái)說(shuō)，可讀性有時(shí)候要比代碼本身的效率要重要的多。
前序遍歷：根結(jié)點(diǎn) ---> 左子樹(shù) ---> 右子樹(shù)
中序遍歷：左子樹(shù)---> 根結(jié)點(diǎn) ---> 右子樹(shù)
后序遍歷：左子樹(shù) ---> 右子樹(shù) ---> 根結(jié)點(diǎn)
層次遍歷：只需按層次遍歷即可

image.png

前序遍歷：1 2 4 5 7 8 3 6
中序遍歷：4 2 7 5 8 1 3 6
后序遍歷：4 7 8 5 2 6 3 1
層次遍歷：1 2 3 4 5 6 7 8

2.2 二叉樹(shù)遍歷算法

public void preOrderTraverse1(TreeNode root) {
        if (root != null) {
            System.out.print(root.val+"  ");
            preOrderTraverse1(root.left);
            preOrderTraverse1(root.right);
        }
}
public void inOrderTraverse1(TreeNode root) {
        if (root != null) {
            inOrderTraverse1(root.left);
            System.out.print(root.val+"  ");
            inOrderTraverse1(root.right);
        }
}

public void postOrderTraverse1(TreeNode root) {
        if (root != null) {
            postOrderTraverse1(root.left);
            postOrderTraverse1(root.right);
            System.out.print(root.val+"  ");
        }
}
// 其實(shí)深度遍歷就是上面的前序、中序和后序。但是為了保證與廣度優(yōu)先遍歷相照應(yīng)，也寫(xiě)在這。代碼也比較好理解，其實(shí)就是前序遍歷


public void depthOrderTraverse(TreeNode root) {
        if (root == null) {
            return;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val+"  ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
}