連結清單及常見算法題

作為線性表的兩種存儲方式 —— 連結清單和數組，這對相愛相殺的好基友有着各自的優缺點。接下來，我們梳理一下這兩種方式。

數組，所有元素都連續的存儲于一段記憶體中，且每個元素占用的記憶體大小相同。這使得數組具備了通過下标快速通路資料的能力。

但連續存儲的缺點也很明顯，增加容量，增删元素的成本很高，時間複雜度均為 O(n)。

增加數組容量需要先申請一塊新的記憶體，然後複制原有的元素。如果需要的話，可能還要删除原先的記憶體。

删除元素時需要移動被删除元素之後的所有元素以保證所有元素是連續的。增加元素時需要移動指定位置及之後的所有元素，然後将新增元素插入到指定位置，如果容量不足的話還需要先進行擴容操作。

總結一下數組的優缺點：

• 優點：可以根據偏移實作快速的随機讀寫。
• 缺點：擴容，增删元素極慢。

連結清單，由若幹個結點組成，每個結點包含資料域和指針域。結點結構如下圖所示：

一般來講，連結清單中隻會有一個結點的指針域為空，該結點為尾結點，其他結點的指針域都會存儲一個結點的記憶體位址。連結清單中也隻會有一個結點的記憶體位址沒有存儲在其他結點的指針域，該結點稱為頭結點。

連結清單的存儲方式使得它可以高效的在指定位置插入與删除，時間複雜度均為 O(1)。

在結點 p 之後增加一個結點 q 總共分三步：

1. 申請一段記憶體用以存儲 q (可以使用記憶體池避免頻繁申請和銷毀記憶體)。
2. 将 p 的指針域資料複制到 q 的指針域。
3. 更新 p 的指針域為 q 的位址。

   

   删除結點 p 之後的結點 q 總共分兩步：

1.将 q 的指針域複制到 p 的指針域。

2. 釋放 q 結點的記憶體

連結清單主要代碼

#include <bits/stdc++.h>

using namespace std;

//定義一個結點模闆
template<typename T>
struct Node {
	T data;
	Node *next;
	Node() : next(nullptr) {}
	Node(const T &d) : data(d), next(nullptr) {}
};

//删除 p 結點後面的元素
template<typename T>
void Remove(Node<T> *p) {
	if (p == nullptr || p->next == nullptr) {
		return;
	}
	auto tmp = p->next->next;
	delete p->next;
	p->next = tmp;
}

//在 p 結點後面插入元素
template<typename T>
void Insert(Node<T> *p, const T &data) {
	auto tmp = new Node<T>(data);
	tmp->next = p->next;
	p->next = tmp;
}

//周遊連結清單
template<typename T, typename V>
void Walk(Node<T> *p, const V &vistor) {
	while(p != nullptr) {
		vistor(p);
		p = p->next;
	}
}

int main() {
	auto p = new Node<int>(1);
	Insert(p, 2);
	int sum = 0;
	Walk(p, [&sum](const Node<int> *p) -> void { sum += p->data; });
	cout << sum << endl;
	Remove(p);
	sum = 0;
	Walk(p, [&sum](const Node<int> *p) -> void { sum += p->data; });
	cout << sum << endl;
	return 0;
}

           

面試問題總結

無法高效擷取長度，無法根據偏移快速通路元素，是連結清單的兩個劣勢。然而面試的時候經常碰見諸如擷取倒數第k個元素，擷取中間位置的元素，判斷連結清單是否存在環，判斷環的長度等和長度與位置有關的問題。這些問題都可以通過靈活運用雙指針來解決。

Tips：雙指針并不是固定的公式，而是一種思維方式~

先來看"倒數第k個元素的問題"。設有兩個指針 p 和 q，初始時均指向頭結點。首先，先讓 p 沿着 next 移動 k 次。此時，p 指向第 k+1個結點，q 指向頭節點，兩個指針的距離為 k 。然後，同時移動 p 和 q，直到 p 指向空，此時 q 即指向倒數第 k 個結點。可以參考下圖來了解

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *p = head, *q = head; //初始化
        while(k--) {   //将 p指針移動 k 次
            p = p->next;
        }
        while(p != nullptr) {//同時移動，直到 p == nullptr
            p = p->next;
            q = q->next;
        }
        return q;
    }
};
           

擷取中間元素的問題。設有兩個指針 fast 和 slow，初始時指向頭節點。每次移動時，fast向後走兩次，slow向後走一次，直到 fast 無法向後走兩次。這使得在每輪移動之後。fast 和 slow 的距離就會增加一。設連結清單有 n 個元素，那麼最多移動 n/2 輪。當 n 為奇數時，slow 恰好指向中間結點，當 n 為 偶數時，slow 恰好指向中間兩個結點的靠後一個(可以考慮下如何使其指向前一個結點呢？)。

下述代碼實作了 n 為奇數時慢指針指向結點。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *p = head, *q = head;
        while(q != nullptr && q->next != nullptr) {
            p = p->next;
            q = q->next->next;
        }
        return p;
    } 
};

           

是否存在環的問題。如果将尾結點的 next 指針指向其他任意一個結點，那麼連結清單就存在了一個環。

上一部分中，總結快慢指針的特性 —— 每輪移動之後兩者的距離會加一。下面會繼續用該特性解決環的問題。

當一個連結清單有環時，快慢指針都會陷入環中進行無限次移動，然後變成了追及問題。想象一下在操場跑步的場景，隻要一直跑下去，快的總會追上慢的。當兩個指針都進入環後，每輪移動使得慢指針到快指針的距離增加一，同時快指針到慢指針的距離也減少一，隻要一直移動下去，快指針總會追上慢指針。

根據上述表述得出，如果一個連結清單存在環，那麼快慢指針必然會相遇。實作代碼如下：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while(fast != nullptr) {
            fast = fast->next;
            if(fast != nullptr) {
                fast = fast->next;
            }
            if(fast == slow) {
                return true;
            }
            slow = slow->next;
        }
        return nullptr;
    }
};
           

最後一個問題，如果存在環，如何判斷環的長度呢？方法是，快慢指針相遇後繼續移動，直到第二次相遇。兩次相遇間的移動次數即為環的長度。

原文連結

力扣大佬寫的