代码随想录第三天 | 链表

链表理论知识

链接:　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 为链表当前长度，即 addAtHead，addAtTail 和 addAtIndex 已调用次数之和，addAtIndex 消耗 O(index)。

空间复杂度：所有函数的单次调用空间复杂度均为 O(1)，总体空间复杂度为 O(n)，其中 n 为 addAtHead，addAtTail 和 addAtIndex 调用次数之和。

错误点

1. 在调用addAtIndex函数时, 多次向头部插入时出错, 除判断head_ == nullptr外还需要判断index == 0
2. 插入和删除的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;
}