阅读量:0
要实现高效的插入操作,可以使用双向链表(doubly linked list)来实现ListNode。双向链表可以在O(1)的时间复杂度内进行插入操作。
以下是一个简单的C++示例代码:
#include <iostream> struct ListNode { int val; ListNode* prev; ListNode* next; ListNode(int x) : val(x), prev(nullptr), next(nullptr) {} }; class LinkedList { public: LinkedList() : head(nullptr), tail(nullptr) {} void insert(int val) { ListNode* newNode = new ListNode(val); if (head == nullptr) { head = newNode; tail = newNode; } else { tail->next = newNode; newNode->prev = tail; tail = newNode; } } void print() { ListNode* current = head; while (current != nullptr) { std::cout << current->val << " "; current = current->next; } std::cout << std::endl; } private: ListNode* head; ListNode* tail; }; int main() { LinkedList list; list.insert(1); list.insert(2); list.insert(3); list.print(); return 0; }
在这个示例中,当插入一个新的节点时,只需要将新节点连接到链表的尾部,而不需要遍历整个链表。这样就能在O(1)的时间复杂度内完成插入操作。