社交网站 源码,青岛网页设计 学校,怎么弄一个公司网站,seo推广薪资文章目录 链表理论知识定义链表删除链表 Leetcode203 移除链表元素代码实现 Leetcode707 设计链表代码实现复杂度分析错误点 Leetcode206 反转链表新建链表双指针法 链表理论知识 链接: https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.h… 文章目录 链表理论知识定义链表删除链表 Leetcode203 移除链表元素代码实现 Leetcode707 设计链表代码实现复杂度分析错误点 Leetcode206 反转链表新建链表双指针法 链表理论知识 链接: https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E9%93%BE%E8%A1%A8%E7%9A%84%E7%B1%BB%E5%9E%8B 定义链表
// 单链表的节点定义
struct ListNode {int data; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode(int val) : data(val), next(nullptr) {} // 节点的构造函数
};// 双链表的节点定义
struct DoublyLinkedListNode {int data;DoublyLinkedListNode * prev;DoublyLinkedListNode * next;DoublyLinkedListNode(int val): data(val), prev(nullptr), next(nullptr) {}
};// 新建一个节点
ListNode* head new ListNode(5);删除链表
需手动释放这个D节点释放这块内存 链表的增添和删除都是O(1)操作也不会影响到其他节点. 如果删除最后一个节点需要从头节点查找到第四个节点通过next指针进行删除操作查找的时间复杂度是O(n)
// 删除头节点
ListNode * tmp head;
head head-next;
delete tmp;Leetcode203 移除链表元素 链接: https://leetcode.cn/problems/remove-linked-list-elements/description/ 代码实现
ListNode* removeElements(ListNode* head, int val) {// 循环删除满足要求的头节点while (head ! nullptr head-val val) {ListNode * tmp head;head head-next;delete tmp;}ListNode* current_node head;// 该循环内已经包含了最后一个节点需要删除的情况while (current_node ! nullptr current_node-next ! nullptr) {if (current_node-next-val val) {ListNode* tmp current_node-next;current_node-next current_node-next-next;delete tmp;} else {current_node current_node-next;}}return head;
}Leetcode707 设计链表 链接: https://leetcode.cn/problems/design-linked-list/description/ 代码实现
class MyLinkedList {
public:struct ListNode {int val;ListNode * next;ListNode(int data): val(data), next(nullptr) {}};MyLinkedList() {}int get(int index) {if (index size_ || index 0) {return -1;}ListNode* current_node head_;while (index-- 0) {current_node current_node-next;}return current_node-val;}void addAtHead(int val) {ListNode * new_node new ListNode(val);new_node-next head_;head_ new_node;size_;}void addAtTail(int val) {ListNode * current_node head_;if (current_node nullptr) {addAtHead(val);return;}while (current_node-next ! nullptr) {current_node current_node-next;}ListNode * new_node new ListNode(val);current_node-next new_node;size_;}void addAtIndex(int index, int val) {if (index size_ || index 0) {return;}if (head_ nullptr || index 0) {addAtHead(val);return;}ListNode * current_node head_;while (--index 0) {current_node current_node-next;}ListNode * new_node new ListNode(val);new_node-next current_node-next;current_node-next new_node;size_;}void deleteAtIndex(int index) {if (index 0 || index size_) {return;}if (index 0) {ListNode * tmp head_;head_ head_-next;delete tmp;} else {ListNode * current_node head_;while (--index 0) {current_node current_node-next;}ListNode * tmp current_node-next;current_node-next current_node-next-next;delete tmp;}size_--;}// 打印链表void printList() const {ListNode* temp head_;while (temp ! nullptr) {std::cout temp-val - ;temp temp-next;}std::cout nullptr std::endl;}private:ListNode * head_{nullptr};int size_{0};
};/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList* obj new MyLinkedList();* int param_1 obj-get(index);* obj-addAtHead(val);* obj-addAtTail(val);* obj-addAtIndex(index,val);* obj-deleteAtIndex(index);*/复杂度分析
时间复杂度初始化消耗 O(1)get 消耗 O(index)addAtHead 消耗 O(1)addAtTail 消耗 O(n)其中 n 为链表当前长度即 addAtHeadaddAtTail 和 addAtIndex 已调用次数之和addAtIndex 消耗 O(index)。
空间复杂度所有函数的单次调用空间复杂度均为 O(1)总体空间复杂度为 O(n)其中 n 为 addAtHeadaddAtTail 和 addAtIndex 调用次数之和。
错误点
在调用addAtIndex函数时, 多次向头部插入时出错, 除判断head_ nullptr外还需要判断index 0插入和删除的while循环条件和get中的条件不同
Leetcode206 反转链表 链接: https://leetcode.cn/problems/reverse-linked-list/description/ 代码随想录解析: https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html#%E6%80%9D%E8%B7%AF 时间复杂度: O(N) 空间复杂度: O(1) 新建链表
会造成内存浪费
双指针法
需特别注意, 在初始化prev和cur指针后, 需将prev-next更新为nullptr, 避免循环嵌套
ListNode* reverseList(ListNode* head) {if (head nullptr || head-next nullptr) {return head;}ListNode * prev head;ListNode * cur head-next;prev-next nullptr;while (cur ! nullptr) {ListNode * tmp cur-next;cur-next prev;prev cur;cur tmp;}return prev;
}
