【秋招】嵌入式面試八股文 - 最全專欄

1. 鏈表基礎(chǔ)概念

Q: 什么是鏈表？鏈表有哪些類型？

鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)，由一系列節(jié)點組成，每個節(jié)點包含數(shù)據(jù)字段和指向下一個節(jié)點的引用（指針）。

常見類型：

• 單向鏈表：每個節(jié)點只有一個指向下一節(jié)點的指針
• 雙向鏈表：每個節(jié)點有兩個指針，分別指向前一個和后一個節(jié)點
• 循環(huán)鏈表：最后一個節(jié)點指向第一個節(jié)點，形成環(huán)
• 雙向循環(huán)鏈表：結(jié)合雙向鏈表和循環(huán)鏈表特性

Q: 鏈表與數(shù)組的區(qū)別是什么？各自的優(yōu)缺點？

區(qū)別與優(yōu)缺點：

2. 鏈表基本操作

Q: 如何實現(xiàn)單鏈表的創(chuàng)建、插入、刪除和遍歷？

// 定義鏈表節(jié)點結(jié)構(gòu)
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 創(chuàng)建新節(jié)點
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("內(nèi)存分配失敗\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在鏈表頭部插入節(jié)點
Node* insertAtBeginning(Node* head, int data) {
    Node* newNode = createNode(data);
    newNode->next = head;
    return newNode;
}

// 在鏈表尾部插入節(jié)點
Node* insertAtEnd(Node* head, int data) {
    Node* newNode = createNode(data);
    
    // 如果鏈表為空，新節(jié)點就是頭節(jié)點
    if (head == NULL) {
        return newNode;
    }
    
    // 找到最后一個節(jié)點
    Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    
    // 在最后一個節(jié)點后添加新節(jié)點
    temp->next = newNode;
    return head;
}

// 刪除指定值的節(jié)點
Node* deleteNode(Node* head, int key) {
    // 如果鏈表為空，直接返回
    if (head == NULL) {
        return NULL;
    }
    
    // 如果頭節(jié)點就是要刪除的節(jié)點
    if (head->data == key) {
        Node* temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    
    // 查找要刪除的節(jié)點
    Node* current = head;
    Node* prev = NULL;
    
    while (current != NULL && current->data != key) {
        prev = current;
        current = current->next;
    }
    
    // 如果找到了要刪除的節(jié)點
    if (current != NULL) {
        prev->next = current->next;
        free(current);
    }
    
    return head;
}

// 遍歷鏈表
void traverseList(Node* head) {
    Node* current = head;
    
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 釋放鏈表內(nèi)存
void freeList(Node* head) {
    Node* current = head;
    Node* next;
    
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
}

Q: 如何實現(xiàn)雙向鏈表的基本操作？

// 定義雙向鏈表節(jié)點結(jié)構(gòu)
typedef struct DNode {
    int data;
    struct DNode* prev;
    struct DNode* next;
} DNode;

// 創(chuàng)建新節(jié)點
DNode* createDNode(int data) {
    DNode* newNode = (DNode*)malloc(sizeof(DNode));
    if (newNode == NULL) {
        printf("內(nèi)存分配失敗\n");
        exit(1);
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// 在雙向鏈表頭部插入節(jié)點
DNode* insertAtBeginningDLL(DNode* head, int data) {
    DNode* newNode = createDNode(data);
    
    if (head == NULL) {
        return newNode;
    }
    
    newNode->next = head;
    head->prev = newNode;
    return newNode;
}

// 在雙向鏈表尾部插入節(jié)點
DNode* insertAtEndDLL(DNode* head, int data) {
    DNode* newNode = createDNode(data);
    
    if (head == NULL) {
        return newNode;
    }
    
    DNode* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    
    temp->next = newNode;
    newNode->prev = temp;
    return head;
}

// 刪除雙向鏈表中的節(jié)點
DNode* deleteNodeDLL(DNode* head, int key) {
    if (head == NULL) {
        return NULL;
    }
    
    // 如果頭節(jié)點是要刪除的節(jié)點
    if (head->data == key) {
        DNode* temp = head;
        head = head->next;
        
        if (head != NULL) {
            head->prev = NULL;
        }
        
        free(temp);
        return head;
    }
    
    DNode* current = head;
    
    while (current != NULL && current->data != key) {
        current = current->next;
    }
    
    if (current == NULL) {
        return head; // 沒找到要刪除的節(jié)點
    }
    
    // 調(diào)整前一個節(jié)點的next指針
    if (current->prev != NULL) {
        current->prev->next = current->next;
    }
    
    // 調(diào)整后一個節(jié)點的prev指針
    if (current->next != NULL) {
        current->next->prev = current->prev;
    }
    
    free(current);
    return head;
}

// 遍歷雙向鏈表
void traverseDLL(DNode* head) {
    DNode* current = head;
    
    printf("NULL <-> ");
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

3. 鏈表經(jīng)典問題

Q: 如何檢測鏈表中是否有環(huán)？

Floyd的龜兔算法（快慢指針法）：

bool hasCycle(Node* head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }
    
    Node* slow = head;
    Node* fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;          // 慢指針每次走一步
        fast = fast->next->next;    // 快指針每次走兩步
        
        if (slow == fast) {         // 如果兩個指針相遇，說明有環(huán)
            return true;
        }
    }
    
    return false;  // 如果fast到達鏈表尾部，說明沒有環(huán)
}

Q: 如何找到鏈表的中間節(jié)點？

快慢指針法：

Node* findMiddle(Node* head) {
    if (head == NULL) {
        return NULL;
    }
    
    Node* slow = head;
    Node* fast = head;
    
    // 快指針每次走兩步，慢指針每次走一步
    // 當(dāng)快指針到達鏈表尾部時，慢指針恰好在中間
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;  // 慢指針指向中間節(jié)點
}

Q: 如何反轉(zhuǎn)單鏈表？

迭代方法：

Node* reverseList(Node* head) {
    Node* prev = NULL;
    Node* current = head;
    Node* next = NULL;
    
    while (current != NULL) {
        next = current->next;    // 保存下一個節(jié)點
        current->next = prev;    // 反轉(zhuǎn)當(dāng)前節(jié)點的指針
        prev = current;          // 移動prev指針
        current = next;          // 移動current指針
    }
    
    return prev;  // 新的頭節(jié)點
}

遞歸方法：

Node* reverseListRecursive(Node* head) {
    // 基本情況：空鏈表或只有一個節(jié)點
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    // 遞歸反轉(zhuǎn)剩余部分
    Node* newHead = reverseListRecursive(head->next);
    
    // 改變指針方向
    head->next->next = head;
    head->next = NULL;
    
    return newHead;
}

Q: 如何合并兩個有序鏈表？

Node* mergeTwoLists(Node* l1, Node* l2) {
    // 創(chuàng)建一個啞節(jié)點作為合并鏈表的頭部
    Node dummy;
    Node* tail = &dummy;
    
    while (l1 != NULL && l2 != NULL) {
        if (l1->data <= l2->data) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    // 連接剩余部分
    if (l1 != NULL) {
        tail->next = l1;
    } else {
        tail->next = l2;
    }
    
    return dummy.next;
}

Q: 如何檢測并找到環(huán)的入口點？

Node* detectCycleStart(Node* head) {
    if (head == NULL || head->next == NULL) {
        return NULL;
    }
    
    Node* slow = head;
    Node* fast = head;
    bool hasCycle = false;
    
    // 第一步：檢測是否有環(huán)
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }
    
    if (!hasCycle) {
        return NULL;
    }
    
    // 第二步：找到環(huán)的入口點
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    
    return slow;  // 環(huán)的入口點
}

4. 高級鏈表問題

Q: 如何判斷兩個鏈表是否相交？如何找