面试题：C++链表中指针的基本操作

Question

请用C++实现一个单向链表，并编写函数完成链表节点的插入和删除操作，要求清晰展示指针在这些操作中的使用方式。

Answer 1

#include <iostream>

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 插入节点到链表头部
ListNode* insertAtHead(ListNode* head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    return newNode;
}

// 删除链表中值为val的节点
ListNode* deleteNode(ListNode* head, int val) {
    if (head == nullptr) {
        return nullptr;
    }
    if (head->val == val) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
        return head;
    }
    ListNode* current = head;
    while (current->next != nullptr && current->next->val != val) {
        current = current->next;
    }
    if (current->next != nullptr) {
        ListNode* temp = current->next;
        current->next = current->next->next;
        delete temp;
    }
    return head;
}

// 打印链表
void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

// 释放链表内存
void freeList(ListNode* head) {
    ListNode* current = head;
    ListNode* nextNode;
    while (current != nullptr) {
        nextNode = current->next;
        delete current;
        current = nextNode;
    }
}

int main() {
    ListNode* head = nullptr;
    head = insertAtHead(head, 3);
    head = insertAtHead(head, 2);
    head = insertAtHead(head, 1);

    std::cout << "Original list: ";
    printList(head);

    head = deleteNode(head, 2);
    std::cout << "List after deletion: ";
    printList(head);

    freeList(head);
    return 0;
}

1. 链表节点定义：
   • 定义了ListNode结构体，包含一个整数值val和一个指向下一个节点的指针next。
2. 插入节点到链表头部：
   • insertAtHead函数创建一个新节点newNode，其next指针指向原链表头部head，然后返回新的头部newNode。
3. 删除链表中值为val的节点：
   • 首先检查链表是否为空，如果为空直接返回nullptr。
   • 如果头节点的值就是要删除的值，保存头节点指针到temp，将头节点指向下一个节点，然后释放temp指向的内存，返回新的头节点。
   • 否则，遍历链表，找到值为val的节点的前一个节点current，保存要删除节点的指针到temp，将current的next指针绕过要删除的节点，然后释放temp指向的内存。
4. 打印链表：
   • printList函数遍历链表，依次输出每个节点的值。
5. 释放链表内存：
   • freeList函数遍历链表，依次释放每个节点的内存。
6. 主函数：
   • 创建链表，插入一些节点，打印链表，删除一个节点后再次打印链表，最后释放链表内存。