构造一个不带头结点的单链表

可以这样构造一个不带头结点的单链表：

struct Node {
int val;
Node *next;
};

Node *createList(int arr[], int n) {
if (n == 0) {
return NULL;
}
Node *head = new Node();
head->val = arr[0];
head->next = NULL;
Node *cur = head;
for (int i = 1; i < n; i++) {
Node *node = new Node();
node->val = arr[i];
node->next = NULL;
cur->next = node;
cur = node;
}
return head;
}

这个函数可以接受一个数组和数组长度，返回一个不带头结点的单链表。

相关问题

设计一个不带头结点的单链表类

好的，以下是一个不带头结点的单链表类的基本设计：

class LinkedList {
private:
    struct Node {
        int data;
        Node* next;
        Node(int d) : data(d), next(nullptr) {}
    };
    Node* head; // 头指针
public:
    LinkedList() : head(nullptr) {}
    ~LinkedList() {
        while (head) {
            Node* temp = head->next;
            delete head;
            head = temp;
        }
    }
    void insertFront(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
    }
    void insertBack(int val) {
        Node* newNode = new Node(val);
        if (head == nullptr) {
            head = newNode;
        } else {
            Node* cur = head;
            while (cur->next) {
                cur = cur->next;
            }
            cur->next = newNode;
        }
    }
    void remove(int val) {
        if (head == nullptr) return;
        if (head->data == val) {
            Node* temp = head;
            head = head->next;
            delete temp;
        } else {
            Node* cur = head;
            while (cur->next && cur->next->data != val) {
                cur = cur->next;
            }
            if (cur->next) {
                Node* temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            }
        }       
    }
    void print() {
        Node* cur = head;
        while (cur) {
            cout << cur->data << " ";
            cur = cur->next;
        }
        cout << endl;
    }
};

这个类有两个私有成员：`Node` 结构体和头指针 `head`。`Node` 结构体表示一个单链表节点，包含一个数据成员 `data` 和一个指向下一个节点的指针 `next`。`head` 初始值为 `nullptr`。

公有成员包括构造函数、析构函数、在链表前面插入节点的函数 `insertFront`、在链表后面插入节点的函数 `insertBack`、删除节点的函数 `remove` 和打印链表的函数 `print`。

在 `insertFront` 中，首先创建一个新节点 `newNode`，然后将它的 `next` 指向当前头节点 `head`，最后将 `head` 指向新节点 `newNode`。

在 `insertBack` 中，首先创建一个新节点 `newNode`，然后判断当前链表是否为空。如果为空，将 `head` 指向新节点 `newNode`；否则，找到最后一个节点并将其 `next` 指向新节点 `newNode`。

在 `remove` 中，首先判断当前链表是否为空，或者头节点是否需要删除。如果是，直接删除头节点；否则，找到需要删除的节点的前一个节点 `cur`，将它的 `next` 指向要删除节点的下一个节点，最后删除要删除的节点。

在 `print` 中，从头节点开始遍历整个链表，并输出每个节点的值。

编写函数删除不带头结点单链表head中的第一个值为x的结点，并构造测试用例进行测试

可以使用以下代码来删除不带头结点单链表head中的第一个值为x的结点：

void deleteNode(ListNode* head, int x) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr && curr->val != x) {
        prev = curr;
        curr = curr->next;
    }
    if (curr != nullptr) {
        if (prev != nullptr) {
            prev->next = curr->next;
        } else {
            head = curr->next;
        }
        delete curr;
    }
}

测试用例可以包括以下情况：

- 删除的结点是头结点
- 删除的结点是尾结点
- 删除的结点是中间结点
- 删除的结点不存在

例如：

ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);

deleteNode(head, 2); // 删除中间结点
deleteNode(head, 1); // 删除头结点
deleteNode(head, 4); // 删除尾结点
deleteNode(head, 5); // 删除不存在的结点

注意：在实际使用中，需要根据具体情况来确定是否需要传入头结点的指针。如果需要删除头结点，需要更新头结点的指针。