【數據結構入門】數組和鏈表的OJ題（2）

目錄

1.回文鏈表

分析：

代碼：

2.相交鏈表

分析：

代碼：

3.環形鏈表

分析：

代碼：

面試提問：

4.環形鏈表II

分析1：

分析2：

代碼：

5.隨機鏈表的復制

分析：

代碼：

6.對鏈表進行插入排序

分析：

代碼：

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

分析：

代碼：

1.回文鏈表

? ? ? ? 限制時間復雜度是O（n），空間復雜度為O（1）；

給定一個鏈表的?頭節點?head?，請判斷其是否為回文鏈表。

如果一個鏈表是回文，那么鏈表節點序列從前往后看和從后往前看是相同的。

示例 1：

輸入: head = [1,2,3,3,2,1]
輸出: true

示例 2：

輸入: head = [1,2]
輸出: false

提示：

  • 鏈表 L 的長度范圍為?[1, 105]
  • 0?<= node.val <= 9

分析：

? ? ? ? 先找到中間位置，從中間位置到末尾的鏈表進行逆置，將逆置完畢的鏈表和開始位置到中間位置的鏈表進行比對，若相同那么就是回文鏈表。

1.找到鏈表的中間位置

????????這里使用快慢指針，對于快指針一次走兩步，慢指針一次走一步；

????????如果鏈表元素個數是偶數那么快指針走到NULL停止，如果鏈表元素個數是奇數，快指針走到鏈表最后一個元素停止，停止的條件是:fast->next == NULL || fast == NULL，那么繼續的條件就是取反：fast->next ！=?NULL &&?fast != NULL；

????????如此以來循環結束之后，slow指針指向的就是鏈表的中間位置。

2.逆置鏈表

????????????????使用三個指針，分別指向NULL，head，head->next，這里需要在程序之前判斷鏈表元素的個數為0或者1直接返回頭結點。???????

? ? ? ? n2指向n1，n1更新為n2，n2更新為n3，n3更新為n3->next，當n3為空的時候，終止循環，此時鏈表的最后兩個節點沒有完成逆置，所以需要手動進行逆置。?

逆置完畢之后，n2就是逆置之后的鏈表的頭結點。

3.銜接的問題

當鏈表是偶數的時候，逆置中間的元素，那么此時需要將中間元素的前一個元素的指針進行斷開，奇數也是如此。

????????想要斷開與中間節點的連接，這里還需要知道中間節點的前一個節點，在求中間節點的時候可以設置變量記錄下來，然后使其指向NULL，這樣一來就斷開與中間節點的連接了；

? ? ? ? 最后就是比較回文了，我們發現回文鏈表有可能是奇數也有可能是偶數，如果是偶數就不用擔心比較的方法，如果是奇數，則這里需要按照前半段的鏈表（較短）來比較。

代碼：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
ListNode* reverseList(ListNode* head) {// 如果0、1個節點，返回自身if (head == NULL || head->next == NULL) {return head;}// 定義三個指針ListNode* p1 = NULL;ListNode* p2 = head;ListNode* p3 = head->next;while (p3) {p2->next = p1;p1 = p2;p2 = p3;p3 = p3->next;}// n3為空的時候，最后一次反轉還沒開始p2->next = p1;return p2;
}
bool isPalindrome(struct ListNode* head) {ListNode* fast = head;ListNode* slow = head;ListNode* prev = head; // 中間節點的前一個節點// 鏈表個數為偶數，fast會在NULL，鏈表個數為奇數，fast會在最后一個元素while (fast != NULL && fast->next != NULL) {prev = slow; // 記錄中間節點的前一個節點fast = fast->next->next;slow = slow->next;}prev->next = NULL;                    // 斷開后半部分ListNode* scHead = reverseList(slow); // 翻轉之后的頭結點// 進行比較，如果是奇數那么兩邊的鏈表長度不一致，所以循環按照前半部分鏈表while (head) {if (head->val == scHead->val) {head = head->next;scHead = scHead->next;}else{return false;break;}}return true;}

2.相交鏈表

給定兩個單鏈表的頭節點?headA?和?headB?，請找出并返回兩個單鏈表相交的起始節點。如果兩個鏈表沒有交點，返回?null?。

圖示兩個鏈表在節點?c1?開始相交：

題目數據?保證?整個鏈式結構中不存在環。

注意，函數返回結果后，鏈表必須?保持其原始結構?。

示例 1：

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
解釋：相交節點的值為 8 （注意，如果兩個鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。
在 A 中，相交節點前有 2 個節點；在 B 中，相交節點前有 3 個節點。

示例?2：

輸入：intersectVal?= 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at '2'
解釋：相交節點的值為 2 （注意，如果兩個鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [0,9,1,2,4]，鏈表 B 為 [3,2,4]。
在 A 中，相交節點前有 3 個節點；在 B 中，相交節點前有 1 個節點。

示例?3：

輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。
由于這兩個鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
這兩個鏈表不相交，因此返回 null 。

提示：

  • listA?中節點數目為?m
  • listB?中節點數目為?n
  • 0 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果?listA?和?listB?沒有交點，intersectVal?為?0
  • 如果?listA?和?listB?有交點，intersectVal == listA[skipA + 1] == listB[skipB + 1]

進階：能否設計一個時間復雜度?O(n)?、僅用?O(1)?內存的解決方案？

分析：

? ? ? ? 首先需要計算出每一個鏈表的長度，再計算長度的差值，需要讓長一點的指針走差值那么多步，使得兩個指針處于同一起跑線上，此時同時再進行遍歷，直到兩個指針相同（不是值相同），需要在循環中判斷如果任意一方（因為同步走）的指針是NULL，說明沒有交點，返回空，否則就繼續循環，退出循環的條件是兩個指針不同，如果沒有提前return，說明循環正常結束，那么就直接返回任意一個指針即可。

代碼：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {ListNode* p1 = headA;ListNode* p2 = headB;// 先計算出各自鏈表的長度，鏈表長的可以先走幾步，保證指針在同一個位置int la = 0;int lb = 0;int between = 0;while(p1){p1 = p1->next;la++;}while(p2){p2 = p2->next;lb++;}// 保持同步if(la > lb){between = la - lb;while(between--){headA = headA->next;}}else{between = lb - la;while(between--){headB = headB->next;}}// 同時走while(headA != headB){headA = headA->next;headB = headB->next;if(headA ==NULL){return NULL;}}return headA;
}

3.環形鏈表

給你一個鏈表的頭節點?head?，判斷鏈表中是否有環。

如果鏈表中有某個節點，可以通過連續跟蹤?next?指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos?不作為參數進行傳遞?。僅僅是為了標識鏈表的實際情況。

如果鏈表中存在環?，則返回?true?。 否則，返回?false?。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例?2：

輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環。

提示：

  • 鏈表中節點的數目范圍是?[0, 104]
  • -105 <= Node.val <= 105
  • pos?為?-1?或者鏈表中的一個?有效索引?。

進階：你能用?O(1)（即，常量）內存解決此問題嗎？

分析：

? ? ? ? 帶環鏈表最惡心的地方是在于不能遍歷，這里可以用快慢指針來實現。

快指針先進環，慢指針后進環，如果有環，那么快指針一定能追上慢指針，一旦追上就判定有環。

代碼：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* fast = head;ListNode* slow = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;if(fast == slow){return true;}}return false;
}

面試提問：

請正面快指針如何追上慢指針？為什么快指針的步長是2步，3步行不行，n步行不行？

????????假設兩個指針進環以后他們之間的距離是x，那么slow每走一步，fast就走兩步，那么它們之間的距離就會是x、x-1、x-2.......0

? ? ? ? 那么如果fast指針一次走3步，那么他們之間的距離是x-2、x-4、x-6，此時x如果是奇數那么快慢指針就會永不相遇。

4.環形鏈表II

給定一個鏈表，返回鏈表開始入環的第一個節點。 從鏈表的頭節點開始沿著?next?指針進入環的第一個節點為環的入口節點。如果鏈表無環，則返回?null。

為了表示給定鏈表中的環，我們使用整數?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果?pos?是?-1，則在該鏈表中沒有環。注意，pos?僅僅是用于標識環的情況，并不會作為參數傳遞到函數中。

說明：不允許修改給定的鏈表。

    示例 1：

    輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第二個節點。

    示例?2：

    輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第一個節點。

    示例 3：

    輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環。

    提示：

    • 鏈表中節點的數目范圍在范圍?[0, 104]?內
    • -105 <= Node.val <= 105
    • pos?的值為?-1?或者鏈表中的一個有效索引

    進階：是否可以使用?O(1)?空間解決此題？

    分析1：

    ? ? ? ? 快指針走兩步，慢指針走一步，總會在環中相遇，在相遇的節點中斷開，作為頭結點；

    此時非環的鏈表和斷開的鏈表分別作為頭結點，查找單鏈表的交點，那么這個交點就是入環的第一個節點。

    分析2：

    快慢指針進圈之后：假如圈前的長度是L，圈的周長是C，圈開始的地方距離快慢指針相遇點的距離是X。

    慢指針走的距離：L+X

    快指針走的距離：L + C + X

    由于快指針走的距離是慢指針的兩倍就有：

    L + C + X = 2 * (L + X)

    稍微化簡一下：

    C = L+X

    即：

    L = C-X

    那么我們可以這樣做：一個指針從起點出發，一個指針從快慢指針的相遇處出發，兩個指針會走相同的步數L 或者C -X，循環結束后兩個指針會相遇，最后返回任意一個節點即可。

    ? ? ? ? 有沒有例外的情況，這種情況是快指針剛好只走了1圈，那么當圈為2的時候，慢指針走一步，快指針走一圈，這樣的情況，上面的推論就不成立，我們可以再進行推算。

    當慢指針入圈之前，快指針可能走了N圈。

    慢指針走的距離：L+X

    快指針走的距離：L + N*C + X

    由于快指針走的距離是慢指針的兩倍就有：

    L + N*C + X = 2 * (L + X)

    稍微化簡一下：

    N*C = L+X

    即：

    L = N*C-X

    也就是說上面的情況，只是一種特殊的情況，即N=1。

    那么我們可以從快慢相遇點開始、從鏈表的頭開始，當鏈表頭指針走了L的時候，相遇點指針可能走了N圈，具體走了幾圈，我們不關心，我們只需要知道這兩個指針走的路程是一樣的，當這兩個指針。

    代碼：

    /*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* detectCycle(struct ListNode* head) {ListNode* fast = head;ListNode* slow = head;// 1.由于是環，所以快指針慢指針必定重合while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;if(fast == slow)// 后判斷，不然循環開始就跳出了{break;}}// 循環退出有兩種可能// 如果是指針相等退出，這是我們想要的，如果不是，那么說明fast本身為空，或者fast->next為空if(fast == NULL || fast->next == NULL){   // 根本不是環return NULL;}// 2.head和交接點同時出發while(head != fast){head = head->next;fast = fast->next;}//3.此時fast走了若干圈，head走了L的距離相遇，這個節點就是入圈點return head;
}

    5.隨機鏈表的復制

    給你一個長度為?n?的鏈表，每個節點包含一個額外增加的隨機指針?random?，該指針可以指向鏈表中的任何節點或空節點。

    構造這個鏈表的?深拷貝。?深拷貝應該正好由?n?個?全新?節點組成，其中每個新節點的值都設為其對應的原節點的值。新節點的?next?指針和?random?指針也都應指向復制鏈表中的新節點，并使原鏈表和復制鏈表中的這些指針能夠表示相同的鏈表狀態。復制鏈表中的指針都不應指向原鏈表中的節點?。

    例如，如果原鏈表中有?X?和?Y?兩個節點，其中?X.random --> Y?。那么在復制鏈表中對應的兩個節點?x?和?y?，同樣有?x.random --> y?。

    返回復制鏈表的頭節點。

    用一個由?n?個節點組成的鏈表來表示輸入/輸出中的鏈表。每個節點用一個?[val, random_index]?表示：

    • val：一個表示?Node.val?的整數。
    • random_index：隨機指針指向的節點索引（范圍從?0?到?n-1）；如果不指向任何節點，則為??null?。

    你的代碼?只?接受原鏈表的頭節點?head?作為傳入參數。

    示例 1：

    輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

    示例 2：

    輸入：head = [[1,1],[2,1]]
輸出：[[1,1],[2,1]]

    示例 3：

    輸入：head = [[3,null],[3,0],[3,null]]
輸出：[[3,null],[3,0],[3,null]]

    提示：

    • 0 <= n <= 1000
    • -104?<= Node.val <= 104
    • Node.random?為?null?或指向鏈表中的節點。

    分析：

    ? ? ? ? 每一個結點除了next指針之外還有一個隨機指針，這個隨機指針有可能指向任意節點（自己、空、其他），這道題的難點是復制隨機指針，由于新鏈表的空間是全新空間，我們從老鏈表得到了第一個節點的隨機指針，但是怎么和新鏈表的節點進行對應呢？

    1.拷貝節點，鏈接到原節點的后面

    2.處理拷貝節點的隨機指針

    ? ? ? ? 通過上圖我們可以發現，源節點的隨機指針指向的元素的next就是新復制的隨機指針！

    3. 將原鏈表的next指針進行恢復

    首先將原鏈表的next指向復制鏈表的next，然后再進行判斷：如果拷貝鏈表next有值，那么就將next賦值為next->next，如果next為空，直接next賦值為空；拷貝鏈表和原鏈表指針后移。

    4.返回拷貝鏈表即可。

    代碼：

    /*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/
typedef struct Node Node;Node* createNode(Node* sourceNode) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->next = NULL;newNode->random = NULL;newNode->val = sourceNode->val;return newNode;
}
struct Node* copyRandomList(struct Node* head) {// 如果沒有節點直接返回空if(!head){return NULL;}Node* curr = head;// 1.復制節點并且串聯在原鏈表中while (curr) {Node* newNode = createNode(curr);Node* tmp = curr->next;curr->next = newNode;newNode->next = tmp;curr = tmp;}// 2.給隨機鏈表賦值，curr的隨機鏈表的next就是復制節點的隨機鏈表curr = head;while (curr !=NULL && curr->next != NULL ) {if(curr->random != NULL){curr->next->random = curr->random->next;}else{curr->next->random = NULL;}curr = curr->next->next;}// 3.斷開連接Node* copyHead = head->next;Node* copyCurr = copyHead;curr = head;while (curr) {curr->next = copyCurr->next;if(copyCurr->next !=NULL){copyCurr->next = copyCurr->next->next;}else{copyCurr->next = NULL;}// 移動指針curr = curr->next;copyCurr = copyCurr->next;}return copyHead;
}

    6.對鏈表進行插入排序

    給定單個鏈表的頭?head?，使用?插入排序?對鏈表進行排序，并返回?排序后鏈表的頭?。

    插入排序?算法的步驟:

    1. 插入排序是迭代的，每次只移動一個元素，直到所有元素可以形成一個有序的輸出列表。
    2. 每次迭代中，插入排序只從輸入數據中移除一個待排序的元素，找到它在序列中適當的位置，并將其插入。
    3. 重復直到所有輸入數據插入完為止。

    下面是插入排序算法的一個圖形示例。部分排序的列表(黑色)最初只包含列表中的第一個元素。每次迭代時，從輸入數據中刪除一個元素(紅色)，并就地插入已排序的列表中。

    對鏈表進行插入排序。

    示例 1：

    輸入: head = [4,2,1,3]
輸出: [1,2,3,4]

    示例?2：

    輸入: head = [-1,5,3,4,0]
輸出: [-1,0,3,4,5]

    提示：

    • 列表中的節點數在?[1, 5000]范圍內
    • -5000 <= Node.val <= 5000

    分析：

    ? ? ? ? 插入排序的原理就是，先把第一個數當做是有序的，后面的數字跟第一個數字進行比較，如果比第一個數字大那么就放在第一個數字后面，如果比第一個數字小那么就放在第一個數字前面，此時鏈表中有兩個數，這兩個數是有序的，那么第三個數只需要從頭開始遍歷即可，插入到合適的位置。

    以下是代碼的梳理：

    ①判斷鏈表中若有1個或0個節點，那么不用排序，直接返回本身；

    ②將鏈表劃分為兩個鏈表，一個是待排序的鏈表，一個是已經有序的鏈表，需要從待排序的鏈表中取節點放到未排序的鏈表中；

    ③將未排序的鏈表的頭結點初始化為已排序的鏈表的頭結點，那么未排序的鏈表的頭結點更新為之前頭結點的下一個節點，然后把已排序的鏈表的頭結點的next置為NULL；

    ④遍歷未排序的鏈表，當當前節點的值比已經排序的鏈表的頭結點的值還要小，說明當前值需要作為已經排序鏈表的頭結點（頭插）；

    ⑤另一種情況（中間插入）：遍歷已排序的鏈表，如果有節點比當前節點的值還要大（或者相等），說明此時應該插入已排序的當前節點之前，所以需要定義一個prev來保存已排序鏈表的節點的前一個節點，prev從已排序節點的頭結點開始即可，因為頭插的情況已經處理了，最近的一個節點是頭結點的下一個節點。

    ⑥如果沒有找到比未排序的當前節點大的節點，已排序的兩個指針prev和curr就一直往后走，當curr為空退出循環，若找到了就在curr之前進行插入，使用break主動退出循環。

    ⑦此時退出循環的可能有兩種，要么自己主動插入后退出循環，要么沒有找到比未排序的當前節點更大的節點，導致sortedCurr為空，我們只需要對后者進行處理，后者說明需要將curr插入到已排序節點的最后面，即尾插。

    ⑧插入完畢之后需要在while大循環的最后將curr指針向后移動，這里就需要在循環開始之前將curr的next節點進行保存，以便移動。

    ⑨直接返回已排序鏈表的頭結點即可。

    代碼：

    /*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* insertionSortList(struct ListNode* head) {// 如果只有一個節點或空鏈表，直接返回本身if(head == NULL || head->next == NULL){return head;}// 分成兩個區域，排序區和未排序區// 取出未排序區的第一個節點作為排序區的第一個節點ListNode* sortedHead = head; head = head->next;sortedHead->next = NULL;ListNode* curr = head; // 未排序區的頭指針// 遍歷未排序區的每一個節點進行插入while(curr){// 保存curr的下一個節點方便迭代ListNode* next = curr->next;// 當前元素比排序區域頭結點還要小，頭插if(curr->val < sortedHead->val){curr->next = sortedHead;sortedHead = curr;}else{// 中間插入,遍歷已排序的鏈表// 找到一個節點比當前節點要大，當前節點就插在這個節點的前面/*因為頭插的情況已經判斷過了，所以最早的插入是頭節點的后面，所以prev直接是頭而curr是頭的下一個節點*/ListNode* sortedPrev = sortedHead;ListNode* sortedCurr = sortedHead->next;while(sortedCurr){// 插在prev和sortedcurr之間if(sortedCurr->val >= curr->val){sortedPrev->next = curr;curr->next = sortedCurr;break;}else{// 如果沒有找到，那就指針后移sortedPrev = sortedCurr;sortedCurr = sortedCurr->next;}}// 出循環有兩種可能，要么是沒插入，要么是插入了提前退出循環// 當sortedCurr為空的時候，說明此時沒有插入，只能尾插if(sortedCurr == NULL){sortedPrev->next = curr;curr->next = NULL;}}// 當前curr插入完畢之后，迭代curr = next;}return sortedHead;
}

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

    給定一個已排序的鏈表的頭?head?，?刪除原始鏈表中所有重復數字的節點，只留下不同的數字?。返回?已排序的鏈表?。

    示例 1：

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

    示例 2：

    輸入：head = [1,1,1,2,3]
輸出：[2,3]

    提示：

    • 鏈表中節點數目在范圍?[0, 300]?內
    • -100 <= Node.val <= 100
    • 題目數據保證鏈表已經按升序?排列

    分析：

    ①一般情況：定義三個指針，判斷curr和next是否相同，如果相同那么就移動next，如果不同那就free掉curr到next之間的所有結點，然后將prev指向next，最后再三個指針一起動；

    ②特殊情況：當鏈表的頭全部相等，那么按照上面的邏輯就是當next和curr不相同的時候，prev的next指向next，如此以來就會空指針的解引用。

    所以我們不能直接將prev指向next，如果不為空才能指向，若為空那么需要重新更換頭結點。

     // 防止開始的幾個元素是相同的，此時prev是空，就會報錯if(prev != NULL){// prev需要指向nextprev->next;}else{// 如果prev是空，又要刪掉前面相同的內容,直接換頭head = next;}

    ③特殊情況：當鏈表的尾全部相等，此時如果單純的比較cur和next，全部相同，那么next就會一直走到NULL，最后依然會對NULL進行解引用。

    這里需要增加一個條件：

    是因為，當末尾元素相同的時候，next和curr都是NULL，此時再進行while判斷就會對空指針解引用。

    當next指針后移的時候，也需要進行判斷，若指針為NULL，那么就會對空指針解引用，加上條件，在最外層的循環會直接退出。

    代碼：

    ? ? ? ??

     typedef struct ListNode ListNode;
struct ListNode* deleteDuplicates(struct ListNode* head) {if(head == NULL || head->next == NULL){return head; // 0或1個節點不需要刪除，直接返回}ListNode* prev = NULL;ListNode* curr = head;ListNode* next = head->next;while(next){// 如果不相等，三個指針同時后移if(curr->val != next->val){prev = curr;curr = next;next = next->next;}else{// 如果curr和next相等，next要移動到不相等為止，若尾元素相同，那么next會走到NULL，判斷的時候會出現空指針解引用// 這里加一個條件next不能為空while(next != NULL && curr->val == next->val){next = next->next;}// 循環結束后，curr和next的值不相等或者next走到null了// 防止開始的幾個元素是相同的，此時prev是空，就會報錯if(prev != NULL){// prev需要指向nextprev->next = next;}else{// 如果prev是空，又要刪掉前面相同的內容,直接換頭head = next;}// curr需要移動到next，并且在移動的過程中釋放內存while(curr != next){ListNode* trash = curr;curr = curr->next;free(trash);}if(next != NULL){next = next->next; }}}return head;
}

    本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
    如若轉載，請注明出處：http://www.pswp.cn/bicheng/92233.shtml
    繁體地址，請注明出處：http://hk.pswp.cn/bicheng/92233.shtml
    英文地址，請注明出處：http://en.pswp.cn/bicheng/92233.shtml

    如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

    相關文章

    文件包含篇

    文件包含篇

    web78 第一題filter偽協議直接讀源碼即可 ?filephp://filter/convert.base64-encode/resourceflag.php web79 flag.php的php無法用大小寫繞過&#xff0c;所以用Php://input只讀流 import requests url "http://fadb524a-f22d-4747-a35c-82f71e84bba7.challenge.ctf.sho…
    閱讀更多...
    互作蛋白組學技術對比：鄰近標記與傳統IP-MS、Pull down-MS優勢對比

    互作蛋白組學技術對比：鄰近標記與傳統IP-MS、Pull down-MS優勢對比

    在生命科學領域&#xff0c;蛋白質間的相互作用構成了生命活動的核心網絡&#xff0c;驅動著信號傳導、基因調控、代謝途徑等關鍵過程。為了繪制這幅復雜的“分子互作地圖”&#xff0c;科學家們開發了多種技術&#xff0c;其中免疫共沉淀結合質譜&#xff08;IP-MS&#xff09…
    閱讀更多...
    （ZipList入門筆記一）ZipList的節點介紹

    （ZipList入門筆記一）ZipList的節點介紹

    ZipList是 Redis 中一種非常緊湊、節省內存的數據結構 Ziplist&#xff08;壓縮列表&#xff09; 的內部內存布局。它被用于存儲元素較少的 List、Hash 和 Zset。 下面我們來詳細介紹每一個節點的含義&#xff1a; 1. zlbytes (ziplist bytes) 含義&#xff1a; 整個壓縮列…
    閱讀更多...
    Unix 發展史概覽

    Unix 發展史概覽

    這里是一個簡明清晰的 Unix 發展史概覽&#xff0c;涵蓋從起源到現代的重要節點和演變過程。Unix 發展史概覽 1. Unix 起源&#xff08;1969年&#xff09; 貝爾實驗室&#xff1a;Ken Thompson 和 Dennis Ritchie 開發出 Unix 操作系統。最初設計目標&#xff1a;簡潔、可移植…
    閱讀更多...
    基于coze studio開源框架二次定制開發教程

    基于coze studio開源框架二次定制開發教程

    目錄 一、 項目介紹 1.1 什么是Coze Studio 1.2 功能清單 1.3對比商業版本 二、 功能定開說明 2.1 技術棧簡介 2.2 項目架構
    閱讀更多...
    RHCE認證題解

    RHCE認證題解

    考前說明請勿更改 IP 地址。DNS 解析完整主機名&#xff0c;同時也解析短名稱。? 所有系統的 root 密碼都是 redhat? Ansible 控制節點上已創建用戶賬戶 devops。可以使用 ssh 訪問? 所需的所有鏡像保存在鏡像倉庫 utility.lab.example.compodman 可使用下述賬號登錄使用 用…
    閱讀更多...
    調用com對象的坑

    調用com對象的坑

    1、諫言 最近我在弄64位調用32位dll的問題&#xff0c;在幾種IPC之間&#xff0c;最后考慮了調用COM 畢竟我們只在windows平臺 2、第一坑–修改編譯后都需要重新注冊&#xff0c;注冊表 一直以為只需要編譯就好了&#xff0c;結果調用沒反應、報錯什么的&#xff0c;需要先撤銷…
    閱讀更多...
    【Python】PyQt 實現 TreeWidget 多級聯動選擇邏輯，打造素材搜索自定義樹形控件！

    【Python】PyQt 實現 TreeWidget 多級聯動選擇邏輯，打造素材搜索自定義樹形控件！

    在開發自己的寫作素材管理工具時，我遇到了一個非常典型但又略顯棘手的 UI 問題： ?? 如何實現一個“可自由勾選分類標簽”的樹形結構界面，支持父子節點自動聯動勾選，提升用戶體驗？ 雖然 PyQt 的 QTreeWidget 是構建多層分類結構的好幫手，但默認卻不具備父子節點的自動級…
    閱讀更多...
    27-數據倉庫與Apache Hive-2

    27-數據倉庫與Apache Hive-2

    1.數倉開發語言概述 理論上來說&#xff0c;任何一款編程語言只要具備讀寫數據、處理數據的能力&#xff0c;都可以用于數倉的開發。比如大家耳熟能詳的C、java、Python等&#xff1b; 關鍵在于編程語言是否易學、好用、功能是否強大。遺憾的是上面所列出的C、Python等編程語言…
    閱讀更多...
    軟件測試——接口自動化

    軟件測試——接口自動化

    測試中的自動化分為兩類&#xff1a; 1.ui自動化&#xff08;web、移動端&#xff09;2.接口自動化 前面的博客中&#xff0c;我們已經講解了web端的ui自動化&#xff0c;感興趣的同學可以去看看&#xff1a;軟件測試——自動化測試常見函數_自動化測試代碼編寫-CSDN博客 今…
    閱讀更多...
    Flask一個用戶同時只能在一處登錄實現

    Flask一個用戶同時只能在一處登錄實現

    場景&#xff1a;web頁面如果多人用同一賬號同時登錄操作&#xff0c;可能會導致數據等的混亂甚至出現故障。并且可能損害開發者的利益。為此&#xff0c;本篇文章就講下如何實現同一賬戶同時僅能一個地方登錄操作。 思路&#xff1a;1. 用戶登陸時生成token&#xff08;uuid.u…
    閱讀更多...
    聯發科芯片組曝高危漏洞：越界寫入缺陷危及智能手機與物聯網設備安全

    聯發科芯片組曝高危漏洞：越界寫入缺陷危及智能手機與物聯網設備安全

    漏洞概況全球領先的芯片組制造商聯發科&#xff08;MediaTek&#xff09;近日發布最新產品安全公告&#xff0c;披露了影響其智能手機、物聯網設備及其他嵌入式系統芯片的多項安全漏洞。高危漏洞分析CVE-2025-20696 作為公告披露的首個且最嚴重的漏洞&#xff0c;該高危缺陷源于…
    閱讀更多...
    Android與Flutter混合開發：頁面跳轉與通信完整指南

    Android與Flutter混合開發：頁面跳轉與通信完整指南

    Android與Flutter混合開發&#xff1a;頁面跳轉與通信完整指南 一、Android跳轉Flutter頁面的實現方式 1. 基礎跳轉方法 &#xff08;1&#xff09;使用全新引擎跳轉&#xff08;每次新建&#xff09; startActivity(FlutterActivity.withNewEngine().initialRoute("/home…
    閱讀更多...
    Web存儲技術詳解：sessionStorage、localStorage與Cookie

    Web存儲技術詳解：sessionStorage、localStorage與Cookie

    一、核心特性對比特性CookielocalStoragesessionStorage存儲大小4KB左右5-10MB5-10MB生命周期可設置過期時間永久存儲&#xff08;除非手動清除&#xff09;會話期間有效&#xff08;標簽頁關閉即清除&#xff09;作用域同源的所有窗口同源的所有窗口僅當前標簽頁自動發送每次H…
    閱讀更多...
    3. 為什么 0.1 + 0.2 != 0.3

    3. 為什么 0.1 + 0.2 != 0.3

    總結 底層是二進制實現概述 在 JavaScript 中&#xff0c;0.1 0.2 的結果并不是精確的 0.3&#xff0c;而是 0.30000000000000004。這個現象并不是 JavaScript 的“bug”&#xff0c;而是由于浮點數在計算機底層的二進制表示方式導致的精度丟失問題。一、計算機如何表示小數&a…
    閱讀更多...
    股票數據接口哪家好？專業評測各主流接口的優勢與不足

    股票數據接口哪家好？專業評測各主流接口的優勢與不足

    Python股票接口實現查詢賬戶&#xff0c;提交訂單&#xff0c;自動交易&#xff08;1&#xff09; Python股票程序交易接口查賬&#xff0c;提交訂單&#xff0c;自動交易&#xff08;2&#xff09; 股票量化&#xff0c;Python炒股&#xff0c;CSDN交流社區 >>> 股票…
    閱讀更多...
    如何用分布式架構視角理解宇宙穩定性？從精細調參到微服務的類比思考

    如何用分布式架構視角理解宇宙穩定性？從精細調參到微服務的類比思考

    在調試一段多線程分布式代碼時&#xff0c;我忽然意識到一個不合理的事實&#xff1a;為什么現實世界這么穩定&#xff1f;為什么沒有“宇宙藍屏”或“感知崩潰”&#xff1f;為什么每天醒來&#xff0c;我們還能看到同樣的物理規律、感知同一個自我&#xff1f;站在程序員的角…
    閱讀更多...
    游戲畫面總是卡頓怎么辦 告別延遲暢玩游戲

    游戲畫面總是卡頓怎么辦 告別延遲暢玩游戲

    玩游戲最讓人頭疼的問題之一就是畫面卡頓&#xff0c;影響操作流暢度與游戲體驗。卡頓可能由硬件性能、系統設置、網絡延遲等多種因素導致。本文將從不同角度出發&#xff0c;為你提供五個有效解決方法&#xff0c;幫助你快速提升游戲流暢度。 一、降低游戲畫質設置 高畫質雖然…
    閱讀更多...
    VUE+SPRINGBOOT從0-1打造前后端-前后臺系統-郵箱重置密碼

    VUE+SPRINGBOOT從0-1打造前后端-前后臺系統-郵箱重置密碼

    在現代Web應用中&#xff0c;密碼重置功能是用戶賬戶安全體系中不可或缺的一部分。本文將詳細介紹如何使用Vue.js前端框架和SpringBoot后端框架實現一個基于郵箱驗證的密碼重置功能。功能概述本密碼重置功能包含以下核心流程&#xff1a;用戶輸入注冊郵箱系統發送驗證碼到該郵箱…
    閱讀更多...
    華為云云產品的發展趨勢：技術創新驅動數字化未來

    華為云云產品的發展趨勢：技術創新驅動數字化未來

    近年來&#xff0c;隨著5G、人工智能&#xff08;AI&#xff09;、大數據、物聯網&#xff08;IoT&#xff09;和邊緣計算等新興技術的快速發展&#xff0c;全球云計算產業正迎來新一輪變革。作為中國領先的云服務提供商&#xff0c;華為云依托華為集團在ICT&#xff08;信息與…
    閱讀更多...
    最新文章

    Copyright @ 2022~2023