链表
- 单链表
双链表
- 每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点
- 可以向前、向后查询
循环链表
- 链表首尾相连
- 可以用来解决约瑟夫环问题
链表的存储方式
在内存中非连续分布，分配机制取决与操作系统的内存管理
链表的定义
// 单链表
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {} // 节点的构造函数
};注意：如果不定义节点的构造函数，则C++默认生成一个构造函数。但是初始化时无法直接给变量赋值
ListNode *head = new ListNode(5); // 使用自己的构造函数
ListNode *head = new ListNode(); // 默认构造函数
head->val = 5;性能分析
名称 空间复杂度 时间复杂度 适用场景
数组 O(n) O(1) 数据量固定，频繁查询，较少增删
链表 O(1) O(n) 数据量不固定，频繁增删，较少查询
leetcode203
// 移除链表元素
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
//ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* remove_elements(ListNode* head, int val) {
// 直接使用链表进行操作
/*
// 删除头节点
while (head != NULL && head->val == val) {
ListNode* tmp = head;
// 头节点后移
head = head->next;
// 删除原来的头节点
delete tmp;
}
// 删除非头节点
ListNode* cur = head;
// 这里如果cur时最后一个节点，且正好 == val，就会进行上面的while循环
while (cur != NULL && cur->next != NULL) {
if (cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
return head;
*/
// 设置虚拟头节点，进行移除操作
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;
while (cur->next != NULL) {
if (cur->next->val == val) {
// 删除符合条件的节点
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
// 当前节点右移
cur = cur->next;
}
}
// 将移除元素后的链表赋值给head
head = dummyHead->next;
// 删除虚拟头节点
delete dummyHead;
return head;
}
};
int main() {
Solution solution;
int val = 5;
ListNode* head = new ListNode(0); // 是否有参数取决于构造函数
// 链表填入数字
}leetcode707
// 设计链表
#include <iostream>
using namespace std;
class MyLinkedList {
public:
// 定义链表节点结构体
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int x) : val(x), next(nullptr) {}
};
// initialize your data structure here
MyLinkedList() {
dummyHead_ = new LinkedNode(0);
size_ = 0;
}
// get the value of the index-th node in the linked list.
// if the index is invalid, return -1
int get(int index) {
if (index > (size_ - 1) || index < 0) {
return -1;
}
LinkedNode* cur = dummyHead_->next;
while (index--) {
cur = cur->next;
}
return cur->val;
}
// add a node of value val before the first element of the linkd list.
// After the insertion, the new node will be the first node of the linked list
void add_at_head(int val) {
LinkedNode* newNode = new LinkedNode(val); // 开空间
newNode->next = dummyHead_->next; // 新节点插入虚拟节点和第一个节点之间
dummyHead_->next = newNode;
size_++;
}
// append a node of value val to the last element of the linked list
void add_at_tail(int val) {
LinkedNode* newNode = new LinkedNode(val); // 为新节点开空间
LinkedNode* cur = dummyHead_;
while (cur->next != nullptr) {
cur = cur->next; // cur为最后一个节点
}
cur->next = newNode; // 将新节点作为cur的下一个节点
size_++; // 链表长度加1
}
// add a node of value val before the index-th node in the linked list.
// if index equals to the length of linked list, the node will be appended to the end of the linked list
void add_index(int index, int val) {
// index大于链表长度，返回空
if (index > size_) {
return;
}
LinkedNode* newNode = new LinkedNode(val);
// cur从虚拟头节点开始，所以newNode插入到cur的后面
LinkedNode* cur = dummyHead_;
while(index--) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
size_++;
}
// delete the index-th node in the linked list, if the index is valid
void delete_at_index(int index) {
// index 不合法
if(index >= size_ || index < 0) {
return;
}
// cur从虚拟节点开始，所以在计算index时，默认少1，所以选择cur后面的节点
LinkedNode* cur = dummyHead_;
while(index--) {
cur = cur->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
// 删除该节点，释放内存
delete tmp;
size_--;
}
// 打印链表
void print_linked_list() {
LinkedNode* cur = dummyHead_;
while (cur->next != nullptr) {
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
}
private:
int size_;
LinkedNode* dummyHead_;
};leetcode206
// 反转链表
#include<iostream>
using namespace std;
class Solution {
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
public:
ListNode* reverse_list(ListNode* head) {
// 双指针法
ListNode* tmp; // cur的下一个节点
ListNode* cur = head;
ListNode* pre = NULL;
while (cur) {
tmp = cur->next; // 下一个节点赋值给tmp，反转时要改变cur->next
// 注意，这里虽然是将next变为pre，实际上是pre赋值给next
cur->next = pre; // 反转操作,将所有的next全部变为pre
// 更新cur和pre指针
pre = cur;
cur = tmp;
}
return pre;
}
};leetcode24
// 两两交换链表中的节点
#include <iostream>
using namespace std;
class Solution {
public:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 建议画图, 主要是链表的指向变化
ListNode* swap_pairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0); // 设置虚拟头节点
dummyHead->next = head;
ListNode* cur = dummyHead;
while (cur->next != nullptr && cur->next->next != nullptr) {
ListNode* tmp = cur->next; // 临时节点
ListNode* tmp1 = cur->next->next->next; // 临时节点
cur->next = cur->next->next;
cur->next->next = tmp;
cur->next->next->next = tmp1;
cur = cur->next->next; // 准备下一轮交换
}
return dummyHead->next;
}
};leetcode19
// 删除倒数第n个节点
#include <iostream>
using namespace std;
class Solution {
public:
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* remove_n_from_end(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0); // 虚拟头节点
dummyHead->next = head;
// 快慢指针
ListNode* fast = dummyHead;
ListNode* slow = dummyHead;
// fast指针先向后走n步
while (n-- && fast != NULL) {
fast = fast->next;
}
fast = fast->next; // fast再提前走一步，让slow指向删除节点的上一个节点
// 当fast指针不指向链表尾部时，fast和slow都向右移
// fast指针和slow指针相差n+1个元素
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
// fast指向null,即slow+1是倒数第n个节点，进行删除
slow->next = slow->next->next;
return dummyHead->next;
// 递归, 找到倒数第n个节点，对该节点进行操作
/*
if (!head) return NULL;
head->next = removeNthFromEnd(head->next, n);
cur++; // 放在递归函数外面，就导致递归结束时，直接head指向了整个链表的最后一个节点，然后cur++，一层一层返回，类似套娃
if (n == cur) return head->next;
return head;
*/
}
};mianshi0207
/*
给定两个单链表的头节点，找出并返回两个单链表相交的起始节点，否则返回null
*/
#include <iostream>
using namespace std;
class Solution {
public:
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* get_intersection_node(ListNode* headA, ListNode* headB) {
// 朴素解法, 计算A、B链表的长度求差，长链表减去差后，两个链表一一对比
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0, lenB = 0; // 节点长度
while (curA != NULL) { // 循环获取节点长度
lenA++;
curA = curA->next;
}
while (curB != NULL) {
lenB++;
curB = curB->next;
}
curA = headA; // 节点还原
curB = headB;
// 让curA为最长链表的头, LenA为其长度
if (lenB > lenA) {
swap(lenA, lenB);
swap(curA, curB);
}
int gap = lenA - lenB; // 获取长度差
while (gap--) {
curA = curA->next; // 调整长链表，使两个链表对齐
}
while (curA != NULL) { // 循环寻找相同的节点
if (curA == curB) {
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;
/* 花里胡哨解法
// 两个链表未相交部分长度为a, b, 相交部分长度为c
// 链表1 = a+c, 链表2 = b+c
// a + c + b = b + c + a,即表1走表2的路，表2走表1的路，最终到达同一个节点
ListNode* a = headA;
ListNode* b = headB;
// 如果相同，则遇到相等的节点了，否则走完a,b，最后都指向NULL
while (a != b) {
a = (a != NULL ? a->next : headB); // 先走表a，再走表b
b = (b != NULL ? b->next : headA); // 先走表b，再走表a
}
return a;
*/
}
};leetcode142
// 环形链表II
#include <iostream>
using namespace std;
class Solution {
public:
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
/*
快慢指针fast移动2次，slow移动一次，如果有环，俩个指针一定会在环中相遇
设头节点到入环点的节点数为x，入环点到相遇点节点数为y，相遇点到入环点的距离为z
则fast = x + y + n(y+z); slow = x + y; 又fast = 2 * slow
即 x = (n-1)(y+z) + z 成立
再设两个指针，分别代表等式两边的节点，两个指针的相遇点就是环形入口节点
*/
ListNode* detect_cycle(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next; // 快节点一次移动两个节点
if (slow == fast) { // 快慢节点相遇，说明有环
ListNode* index1 = fast; // 数学推导的x
ListNode* index2 = head; // 数学推导的(n-1)(y+z) + z
while (index1 != index2) { // 两个指针移动相同距离后相遇点为环形入口点
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return NULL;
}
};
本文由 szr 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Sep 23, 2021 at 10:12 am
|One thing you are going to want to do is always keep an eye open for changes in style. Styles are constantly changing, and you can find out what is new by looking at fashion magazines every now and then. They are likely going to showcase the new trends first.
}{Always remember that there are tons of different options available to you when looking for hair accessories. The sky is really the limit here, and you can choose from different braids and headbands, bows and ribbons, clips and curlers, and much, much more. Your wardrobe should include several hair accessories. A simple ponytail holder goes great with an athletic suit. So before you go out, make sure you're carrying a few accessories with you.
}{Haircare products which offer moisturizer are the best to use on hair which goes frizzy on a humid day. The moisture acts as a protective barrier over the cuticle and can keep your hair looking sleek. Avoid the ingredients wheat or rice that are found in many volumizing products.