链表理论基础
-
链表是一种通过指针串联起的线性结构，每个节点由两部分组成：一个数据域，一个指针域（存放指向下一节点的指针），最后一个节点的指针域指向null。 链表入口节点是头结点head。
-
双链表：两个指针域，指向下一节点和上一节点。（向前向后查询）
-
循环链表：首尾相连。
-
-
存储方式：通过指针，可以散乱的分布数据。
定义链表
手写链表：
// 单链表
struct ListNode
{
int val; // 节点上存储的元素
ListNode *next; // 指向下一节点的指针
ListNide() : val(0), next(NULL){};
ListNode(int x) : val(x), next(NULL){}; // 节点的构造函数
ListNide(int x, ListNode *next) : val(x), next(next){};
}// 单链表
struct ListNode
{
int val; // 节点上存储的元素
ListNode *next; // 指向下一节点的指针
ListNode(int x) : val(x), next(NULL){}; // 节点的构造函数
};
可以不定义构造函数，C++默认生成一个构造函数，但是 这个构造函数不会初始化任何成员变量。
-
通过自己定义构造函数初始化节点：
ListNode* head = new LstNode(5); -
使用默认构造函数初始化节点，如果不定义构造函数，使用默认构造函数的话，在初始化的时候不能直接给变量赋值。
ListNode* head = new ListNode(); head->val = 5;
链表操作
- 删除节点：更改前一节点的next指针指向的位置。在C++中最好再手动释放这个被删除的节点，python，Java就不需要，他们有自己的内存回收机制。
- 添加节点：更改前一节点的next指针指向的位置，以及待插入节点next指针指向的位置。
- 数组添加/删除O(n)，查询O(1)；链表插入删除O(1)，查询O(n）。
202移除链表元素
203. 移除链表元素 - 力扣（LeetCode）
- 定义虚拟头结点dummyHead，遍历节点curr
- 删除节点，
delete tmp;
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 遍历链表,定义虚拟头指针
ListNode* dummyHead = new ListNode(0, head);
ListNode* curr = dummyHead;
while(curr->next){
// 考虑curr->next的值
if(curr->next->val == val){
ListNode* tmp = curr->next;
curr->next = tmp->next;
delete tmp;
}
else{
curr = curr->next;
}
}
head = dummyHead->next;
delete dummyHead;
return head;
}
};
707设计链表
707. 设计链表 - 力扣（LeetCode）
- 构建LinkedNode结构体，设置private初始变量，dummyHead和size
- deleteAtIndex和addAtIndex都是遍历pre指针，初始化为dummyHead，pre->next是需要修改的节点。
class MyLinkedList
{
public:
struct LinkedNode
{
int val;
LinkedNode *next;
LinkedNode(int val) : val(val), next(nullptr) {}
};
// 初始化，设置_dummyHead指针
MyLinkedList()
{
_dummyHead = new LinkedNode(0);
_size = 0;
}
int get(int index)
{
if (index > _size - 1 || index < 0)
{
return -1;
}
LinkedNode *curr = _dummyHead->next;
for (int currentIndex = 0; currentIndex != index; currentIndex++)
{
curr = curr->next;
}
return curr->val;
}
void addAtHead(int val)
{
LinkedNode* newptr = new LinkedNode(val);
newptr->next = _dummyHead->next;
_dummyHead->next = newptr;
_size += 1;
}
void addAtTail(int val)
{
LinkedNode* newptr = new LinkedNode(val);
LinkedNode* curr = _dummyHead;
// 寻找Tail
while(curr->next != nullptr)
curr = curr->next;
curr->next = newptr;
_size += 1;
}
void addAtIndex(int index, int val)
{
if (index > _size || index < 0)
{
return ;
}
LinkedNode *newptr = new LinkedNode(val);
LinkedNode *pre = _dummyHead;
for (int currentIndex = 0; currentIndex < index; currentIndex++)
{
pre = pre->next;
}
newptr->next = pre->next;
pre->next = newptr;
_size += 1;
}
void deleteAtIndex(int index)
{
if (index > _size - 1 || index < 0)
{
return ;
}
LinkedNode *pre = _dummyHead;
for (int currentIndex = 0; currentIndex < index; currentIndex++)
pre = pre->next;
LinkedNode *tmp = pre->next;
pre->next = tmp->next;
delete tmp;
tmp = nullptr;
_size -= 1;
}
void printLinkedList() {
LinkedNode* cur = _dummyHead;
while (cur->next != nullptr) {
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
}
private:
int _size;
LinkedNode* _dummyHead;
};
/**
* 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);
*/
206反转链表
Loading Question… - 力扣（LeetCode）
- 首先定义一个cur指针，指向头结点，**再定义一个pre指针，初始化为null。**不断移动即可。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* curr = head;
ListNode* pre = nullptr;
while(curr){
ListNode* tmp = curr->next;
curr->next = pre;
pre = curr;
curr = tmp;
}
return pre;
}
};
curr = head;
ListNode* pre = nullptr;文章来源：https://www.toymoban.com/news/detail-593421.html
while(curr){
ListNode* tmp = curr->next;
curr->next = pre;
pre = curr;
curr = tmp;
}
return pre;
}
};文章来源地址https://www.toymoban.com/news/detail-593421.html
到了这里，关于day3_203移除链表元素_707设计链表_206反转链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
