《iOS面試題整理》 - 鏈表

鏈表和數(shù)組的區(qū)別

數(shù)組
數(shù)組需要一塊連續(xù)的內(nèi)存空間來存儲(chǔ), 對(duì)內(nèi)存要求比較高

鏈表
通過指針, 將一組零散的內(nèi)存塊串聯(lián)起來使用

鏈表類型

單鏈表、雙向鏈表、循環(huán)鏈表、雙向循環(huán)鏈表

鏈表和數(shù)組的優(yōu)缺點(diǎn)

時(shí)間復(fù)雜度
數(shù)組插入刪除操作時(shí)間復(fù)雜度是 O(n)
鏈表插入刪除操作時(shí)間復(fù)雜度是 O(1)

隨機(jī)訪問第 k 個(gè)元素
數(shù)組 : O(1)
鏈表: O(n)

鏈表使用場(chǎng)景分析

  1. 刪除操作
  • 刪除節(jié)點(diǎn)中“值等于某個(gè)給定值”的節(jié)點(diǎn)
    為了能找到節(jié)點(diǎn), 都需要從頭遍歷, 盡管刪除的時(shí)間復(fù)雜度是 O(1), 但是遍歷查找的時(shí)間是主要的耗時(shí)點(diǎn), 對(duì)應(yīng)的時(shí)間復(fù)雜度為O(n)
  • 刪除特定的節(jié)點(diǎn)
    對(duì)于單鏈表來說, 需要找到前驅(qū)節(jié)點(diǎn), 需要重頭遍歷 , 時(shí)間復(fù)雜度是 O(n)
    對(duì)于雙向鏈表, 已經(jīng)保存前驅(qū)節(jié)點(diǎn), 時(shí)間復(fù)雜度是 O(1)
  1. 插入操作
    指定節(jié)點(diǎn)前面插入一個(gè)節(jié)點(diǎn)
  • 單鏈表, 時(shí)間復(fù)雜度O(n)
  • 雙向鏈表 O(1)
  1. 查詢
    對(duì)于一個(gè)有序鏈表, 雙向鏈表的按值查詢的效率回比單鏈表高, 可以記錄上次查找的位置p, 每次查詢時(shí), 根據(jù)查找的值和p的大小關(guān)系, 決定是往前還是往后查找, 平均只需要查找一半的數(shù)據(jù)

性能分析

數(shù)組簡(jiǎn)單易用, 使用連續(xù)的內(nèi)存空間,可以借助 CPU 的緩存機(jī)制, 預(yù)讀數(shù)組中的數(shù)據(jù), 訪問效率更高。
鏈表在內(nèi)存中不連續(xù), 對(duì) CPU 緩存不友好

數(shù)組的確定是大小固定, 一經(jīng)聲明就要占用整塊連續(xù)的內(nèi)存空間。 如果聲明數(shù)組過大, 導(dǎo)致系統(tǒng)沒有足夠的連續(xù)內(nèi)存空間分配給它, 導(dǎo)致“內(nèi)存不足”. 聲明數(shù)組過小, 可能出現(xiàn)不夠用的情況, 只能再申請(qǐng)更大的內(nèi)存空間, 把原始數(shù)組拷貝過去, 非常耗時(shí)。
鏈表本身沒有限制, 天然支持動(dòng)態(tài)擴(kuò)容

如果代碼對(duì)內(nèi)存的使用非常苛刻, 數(shù)組更合適, 鏈表中的每個(gè)節(jié)點(diǎn)都需要消耗額外的存儲(chǔ)空間存儲(chǔ)下一個(gè)節(jié)點(diǎn)的指針。 對(duì)鏈表進(jìn)行頻繁的插入、刪除操作還會(huì)導(dǎo)致內(nèi)存頻繁的申請(qǐng)和釋放, 容易造成內(nèi)存碎片。 如果是 Java 語(yǔ)言, 可能導(dǎo)致 GC

技巧

  • 插入節(jié)點(diǎn)需要注意操作順序, 刪除節(jié)點(diǎn)需要記得手動(dòng)釋放內(nèi)存空間
  • 利用哨兵, 簡(jiǎn)化鏈表的插入、刪除操作
  • 邊界值處理
    • 鏈表為空
    • 只有一個(gè)節(jié)點(diǎn)
    • 兩個(gè)節(jié)點(diǎn)
    • 處理頭節(jié)點(diǎn)和尾節(jié)點(diǎn)

練習(xí)

  1. 從尾到頭打印鏈表
    思路:
    如果可以改變鏈表結(jié)構(gòu)的話, 翻轉(zhuǎn)鏈表后重頭打印。
    利用棧先進(jìn)后出的性質(zhì), 把鏈表所有數(shù)據(jù)壓棧, 然后按照棧的彈出順序打印。
    既然可以用棧, 那么遞歸的本質(zhì)也是一個(gè)棧結(jié)構(gòu), 用遞歸也是可以打印的。
// 利用棧
void print(ListNode *head) {
   
   Stack *stack = Stack new();
   
   ListNode *node = head;
   while (node ! = NULL) {
       stack.push(node);
       node = node -> next;
   }
   
   while (!stack.empty()) {
       node = stack.top();
       print(" %d\t", node -> value);
       stack.pop();
   }
}

// 遞歸
void recursivePrint(List *head) {
   
   if (head == NULL) return;
   
   if (head -> next != NULL) {
       recursivePrint(head -> next);
   }
   
   printf("%d \t", head -> value);
}
  1. 刪除單鏈表指定節(jié)點(diǎn), 時(shí)間復(fù)雜度 O(1)

思路：

  1. 常規(guī)方法, 遍歷所有節(jié)點(diǎn), 找到指定節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn) p , 即 p -> next = target ， 然后 p -> next = target -> next, 這種操作時(shí)間復(fù)雜度是O(n)
  2. 特殊操作: 把要?jiǎng)h除的節(jié)點(diǎn) p 的下一個(gè)節(jié)點(diǎn) q 的值賦值給p, 再把 p 的 next 指針指向 q 的下一個(gè)節(jié)點(diǎn)

對(duì)于 n -1 個(gè)非尾節(jié)點(diǎn), 可以在O(1) 時(shí)間內(nèi)把下一個(gè)節(jié)點(diǎn)的內(nèi)存復(fù)制到要?jiǎng)h除的節(jié)點(diǎn), 并刪除下一個(gè)節(jié)點(diǎn), 對(duì)于尾節(jié)點(diǎn)而言, 任然需要順序查找 O(n), 總的平均時(shí)間復(fù)雜度是 [(n-1)O(1) + O(n) ] / n, 結(jié)果還是O(1)

  void deleteNode(ListNode *head, ListNode *deleteNode) {
    
    if (head == NULL || deleteNode == NULL) return ;
    
    
    if (deleteNode -> next != NULL) {
        // 刪除的節(jié)點(diǎn)不是尾節(jié)點(diǎn)
        ListNode *temp = deleteNode -> next;
        deleteNode -> value = temp -> value;
        deleteNode -> next = temp -> next;
        
    } else if (head == deleteNode) {
        
        // 刪除的是頭節(jié)點(diǎn)
        head = NULL;
        deleteNode = NULL;
    } else {
        
        // 刪除的是尾節(jié)點(diǎn)
        ListNode *node = head;
        while(node -> next != deleteNode) {
            // 找到前驅(qū)節(jié)點(diǎn)
            node = node -> next;
        }
        
        node -> next = NULL;
        deleteNode = NULL;
    }
    
}
  1. 鏈表中倒數(shù)第 k 個(gè)節(jié)點(diǎn)

思路：

  1. 假設(shè)鏈表的長(zhǎng)度是n，倒數(shù)第 k 個(gè)節(jié)點(diǎn), 如果從頭計(jì)數(shù)的話, 是 n - k + 1 個(gè)節(jié)點(diǎn), 第一次遍歷出節(jié)點(diǎn)的個(gè)數(shù)n, 第二次遍歷就能找到倒數(shù)的第 k 個(gè)節(jié)點(diǎn)

  2. 設(shè)定兩個(gè)指針, 第一個(gè)指針開始遍歷向前走 k - 1 步, 第二個(gè)指針步動(dòng); 從第 k 步開始, 第二個(gè)指針也開始移動(dòng), 兩個(gè)節(jié)點(diǎn)始終保持 k - 1。 當(dāng)?shù)谝粋€(gè)指針走到尾節(jié)點(diǎn)時(shí), 第二個(gè)指針剛好指向倒數(shù)第 k 個(gè)節(jié)點(diǎn)

  ListNode* deleteKThNode(ListNode *head, int k) {
    
    if (!head || k == 0) return 0;
    
    ListNode *slow = head;
    ListNode *fast = head;
    
    for (int i = 0; i < k - 1; i ++) {
        
        if (fast -> next == NULL) return;  // 確保 K 的值小于鏈表長(zhǎng)度
        
        fast = fast -> next;
    }
    
    while (fast -> next != NULL) {
        fast = fast -> next;
        slow = slow -> next;
    }
    
    return slow;
    
}
  1. 翻轉(zhuǎn)鏈表
  //三個(gè)指針
 struct ListNode* reverseList(struct ListNode* head) {

     if (head == NULL) return NULL;

     struct ListNode *pre = NULL;
     struct ListNode *next = NULL;
     struct ListNode *cur = head;

     while (cur != NULL) {
         next = cur -> next;
         cur -> next = pre;
         pre = cur;
         cur = next;
     }

     return pre;
 }

// 遞歸
struct ListNode* reverseList(struct ListNode* head) {
    
    if (head == NULL || head -> next == NULL) return head;
    
    struct ListNode *nextNode = head -> next;
    struct ListNode *reverse_node = reverseList(nextNode);
    nextNode -> next = head;
    head -> next = NULL;
    return reverse_node;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容