數組模擬鏈表

#include<iostream> using namespace std;const int N = 100; // 單鏈表 // head存儲鏈表頭，e[]存儲節點的值，ne[]存儲節點的next指針，idx表示當前用到了哪個節點 int head, e[N], ne[N], idx;// 初始化 void init() {head = -1;idx = 0; }// 在鏈表頭插入一個數a void insert(int a) {//先對新結點賦值e[idx] = a;//新結點的next指針指向前一個結點的next指針的位置ne[idx] = head;//把head的next位置更新為新結點，并且idx++,因為當前idx已經使用head = idx++;// e[idx] = a, ne[idx] = head, head = idx ++ ; }// 將頭結點刪除，需要保證頭結點存在 void remove() {head = ne[head]; }

?????19. 刪除鏈表的倒數第 N 個結點

思路

雙指針,

第一個點可以能被刪除，所以需要一個虛擬頭節點。被刪除的點位于倒數第n的位置，因為是單鏈表，即找到倒數n + 1最后，想要刪除這個節點必須要保留它的前一個節點使其p->next ?= ?p->next->next。返回虛擬頭節點的next?？梢韵仁挂粋€指針移動n步，然后兩個指針

同時移動，第一個指針到達最后的時候，第二個指針恰好在倒數第n + 1的位置
?

code

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/ class Solution { public:ListNode* removeNthFromEnd(ListNode* head, int n) {auto p1 = new ListNode(-1);p1->next = head;auto p2 = p1 , p3 = p1;//先走n步while(n--)p2 = p2->next;//雙指針同時向后移動，兩個指針的距離是確定的while(p2->next){p2 = p2->next;p3 = p3->next;}p3->next = p3->next->next;return p1->next;} };

21. 合并兩個有序鏈表

思路：使用遞歸合并?？谠E判空返，誰小遞歸誰，誰小返回誰。

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/ class Solution { public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 == nullptr)return list2;if(list2 == nullptr)return list1;if(list1->val <= list2->val){list1->next = mergeTwoLists(list1->next,list2);return list1;}else{list2->next = mergeTwoLists(list1,list2->next);return list2;} } };

83. 刪除排序鏈表中的重復元素

思路：相鄰指針。使用相鄰指針，對相鄰兩個結點進行對比，按照題意保留一個相同元素，那么就保留靠前的第一個。如果發現相鄰的相同，則使用相同結點靠后的一個結點的下一個結點覆蓋前面的結點，即p->next = p->next->next ， 如果不同則把當前結點更新為下一個結點p = p->next

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/ class Solution { public:ListNode* deleteDuplicates(ListNode* head) {if(!head)return nullptr;auto p1 = head;while(p1){if(p1->next && p1->next->val == p1->val)p1->next = p1->next->next;else p1 = p1->next;}return head;} };

82. 刪除排序鏈表中的重復元素 II

思路

因為要刪除所有相同的元素，所以head可能被修改，所以創建一個新的虛擬頭節點dump。

需要聲明一個結點p使得它為dump,一個結點q為dump->next。

如果q->val等于p-next->val的情況下，q就繼續前進，直到找到一個與p->val不等的地方停下，判斷當前q與p->next->next是否相等。作用就是（如果相等說明中間只有一個點）,相反執行p->next = q ,刪除中間的內容，最后循環完畢返回dump->next。

code

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/ class Solution { public:ListNode* deleteDuplicates(ListNode* head) {auto dummy = new ListNode(-1);dummy->next = head;auto p = dummy;while (p->next) {auto q = p->next;while (q && q->val == p->next->val) q = q->next;if (p->next->next == q) p = p->next;else p->next = q;}return dummy->next;} };

?

思路

快慢指針算法，邊界判斷如果(快指針的next為空)則為奇數個，如果（快指針為空）則為偶數個。

code

class Solution { public:ListNode* middleNode(ListNode* head) {auto p1 = head, p2 = head;while (p1 && p1->next){p2 = p2->next;p1 = p1->next->next;}return p2;} };

206. 反轉鏈表

思路

雙指針算法，前后指針逐個翻轉，直到最后一個節點，需要考慮邊界問題。

code

//迭代法 class Solution { public:ListNode* reverseList(ListNode* head) {if(!head)return NULL;auto p1 = head, p2 = p1->next;//定義兩個相鄰指針while(p2) {auto p3 = p2->next; //p3存儲p2的后繼節點p2->next = p1; //后面節點指針指向前面的節點p1 = p2;//雙指針統一向后偏移p2 = p3;} head->next=NULL;return p1;} };//遞歸法 class Solution { public:ListNode* reverseList(ListNode* head) {if (!head || !head->next) return head;ListNode *tail = reverseList(head->next);head->next->next = head;head->next = nullptr;return tail;} };

234. 回文鏈表

思路

使用vector來存儲鏈表，然后來檢查其中每一個元素，是否組成回文.。

code

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:bool isPalindrome(ListNode* head) {vector<int> v;while(head){v.push_back(head->val);head = head->next;}// 判斷是否回文for(int i=0; i<v.size()/2; ++i){if(v[i] != v[v.size()-1-i]){return false;}}return true;} };

141. 環形鏈表

思路

快慢指針，如果快指針被慢指針追上一定是環形鏈表。

code

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:bool hasCycle(ListNode *head) {ListNode *l1,*l2;l1=l2=head;while(l1!=NULL && l2!=NULL &&l1->next !=NULL){l1 = l1->next->next;l2 = l2->next;if(l1 == l2)return true;}return false;} };

160. 相交鏈表

思路?

1.哈希表，通過把第一個鏈表的每個結點存入哈希表中，再遍歷第二個鏈表來判斷是否在哈希表中存在，入股存在即為相交結點。

2.雙指針，即兩個指針指向兩個鏈表，同時走，如果相交那么就一定相等；如果不相交那么就是兩條指針最后都為空。如圖

code

//哈希表 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode *> visited;ListNode *temp = headA;while (temp != nullptr) {visited.insert(temp);temp = temp->next;}temp = headB;while (temp != nullptr) {if (visited.count(temp)) {return temp;}temp = temp->next;}return nullptr;} };//雙指針 class Solution { public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (headA == nullptr || headB == nullptr) {return nullptr;}ListNode *pA = headA, *pB = headB;while (pA != pB) {pA = pA == nullptr ? headB : pA->next;pB = pB == nullptr ? headA : pB->next;}return pA;} };

148. 排序鏈表

思路

(歸并排序) 時間：O(nlogn)，空間O(1)
自頂向下遞歸形式的歸并排序，由于遞歸需要使用系統棧，遞歸的最大深度是 logn，所以需要額外 O(logn)的空間。
所以我們需要使用自底向上非遞歸形式的歸并排序算法。
基本思路是這樣的，總共迭代 logn?次：

第一次，將整個區間分成連續的若干段，每段長度是2：[a0,a1],[a2,a3],…[an?1,an?1]， 然后將每一段內排好序，小數在前，大數在后；
第二次，將整個區間分成連續的若干段，每段長度是4：[a0,…,a3],[a4,…,a7],…[an?4,…,an?1]，然后將每一段內排好序，這次排序可以利用之前的結果，相當于將左右兩個有序的半區間合并，可以通過一次線性掃描來完成；
依此類推，直到每段小區間的長度大于等于 n 為止；
另外，當 n?不是2的整次冪時，每次迭代只有最后一個區間會比較特殊，長度會小一些，遍歷到指針為空時需要提前結束。

時間復雜度分析：整個鏈表總共遍歷 logn?次，每次遍歷的復雜度是 O(n)，所以總時間復雜度是 O(nlogn)。
空間復雜度分析：整個算法沒有遞歸，迭代時只會使用常數個額外變量，所以額外空間復雜度是 O(1)

code

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/ class Solution { public:ListNode* sortList(ListNode* head) {int n = 0;for (auto p = head; p; p = p->next) n ++ ;for (int i = 1; i < n; i *= 2) {auto dummy = new ListNode(-1), cur = dummy;for (int j = 1; j <= n; j += i * 2) {auto p = head, q = p;for (int k = 0; k < i && q; k ++ ) q = q->next;auto o = q;for (int k = 0; k < i && o; k ++ ) o = o->next;int l = 0, r = 0;while (l < i && r < i && p && q)if (p->val <= q->val) cur = cur->next = p, p = p->next, l ++ ;else cur = cur->next = q, q = q->next, r ++ ;while (l < i && p) cur = cur->next = p, p = p->next, l ++ ;while (r < i && q) cur = cur->next = q, q = q->next, r ++ ;head = o;}cur->next = NULL;head = dummy->next;}return head;} };

25. K 個一組翻轉鏈表

思路

通過模擬法，模擬整個過程。需要提供雙指針來維護修改某一區間的關系（例如相鄰節點）,

需要注意在修改節點的指針指向之前，要保存原有指向，以便利用。

解題步驟：

1.頭節點可能要被改變，所以需要一個虛擬頭節點

2.遍歷是否夠K個

3.交換K個元素，先將內部反轉，然后處理連接前面部分，再處理連接后面部分

code

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/ class Solution { public:ListNode* reverseKGroup(ListNode* head, int k) {auto dump = new ListNode(-1);dump->next = head;for(auto p = dump;;){auto q = p;//計算后面是否有足夠的k來支撐for(int i = 0; i < k && q;i++) q = q->next;//如果不夠直接結束if(!q)break;auto a = p->next,b = a->next;//如果有k個節點，需要把內部反轉k - 1次for(int i = 0; i < k -1 ;i++){auto c = b->next;b->next = a;a = b, b = c;}auto c = p->next;p->next = a, c->next = b;p = c;}return dump->next;} };

Leetcode 146. LRU 緩存機制

思路:使用雙鏈表模擬隊列，使用哈希表記錄鍵值對

class LRUCache { public:struct Node {int key, val;Node *left, *right;Node(int _key, int _val): key(_key), val(_val), left(NULL), right(NULL) {}}*L, *R;unordered_map<int, Node*> hash;int n;void remove(Node* p) {p->right->left = p->left;p->left->right = p->right;}void insert(Node* p) {p->right = L->right;p->left = L;L->right->left = p;L->right = p;}LRUCache(int capacity) {n = capacity;L = new Node(-1, -1), R = new Node(-1, -1);L->right = R, R->left = L;}int get(int key) {if (hash.count(key) == 0) return -1;auto p = hash[key];remove(p);insert(p);return p->val;}void put(int key, int value) {if (hash.count(key)) {auto p = hash[key];p->val = value;remove(p);insert(p);} else {if (hash.size() == n) {auto p = R->left;remove(p);hash.erase(p->key);delete p;}auto p = new Node(key, value);hash[key] = p;insert(p);}} };/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/

總結

以上是生活随笔為你收集整理的leetcode(链表专题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。