链表相关-Aet

Bingliaolong 2024-09-12 20:28 Aet | 隐藏边栏 | 抢沙发 | 9 0

文章评分 2 次，平均分 5.0 ：

单链表

概述

单链表是一种常见的数据结构，由一组节点（Node）组成，每个节点包含数据部分和指向下一个节点的指针（通常称为 next 指针）
单链表的头节点指向第一个元素，而尾节点的 next 指针指向 nullptr（空指针），表示链表的结束

单链表的节点定义

// 单链表节点的定义

struct Node {

int data; // 数据域

Node* next; // 指向下一个节点的指针

Node(int val) : data(val), next(nullptr) {} // 构造函数，初始化节点

};

单链表的基本操作

创建单链表
1. 创建一个空的单链表，即设置头指针为 nullptr

1	Node* head = nullptr; // 创建一个空链表

插入到头部（头插法）
1. 在链表的头部插入一个节点

void insertAtHead(Node*& head, int value) {

Node* newNode = new Node(value); // 创建新节点

newNode->next = head; // 新节点指向当前头节点

head = newNode; // 更新头节点为新节点

}

插入到尾部（尾插法）
1. 在链表的尾部插入一个节点

void insertAtTail(Node*& head, int value) {

Node* newNode = new Node(value); // 创建新节点

if (!head) { // 如果链表为空

head = newNode; // 直接将新节点作为头节点

return;

}

Node* temp = head; // 遍历找到尾节点

while (temp->next) {

temp = temp->next;

}

temp->next = newNode; // 将尾节点的 next 指向新节点

}

插入到指定位置
1. 在链表的指定位置（索引）插入一个节点，假设索引从 0 开始

void insertAtPosition(Node*& head, int position, int value) {

if (position == 0) { // 插入到头部

insertAtHead(head, value);

return;

}

Node* newNode = new Node(value);

Node* temp = head;

for (int i = 0; i < position - 1 && temp; ++i) {

temp = temp->next; // 遍历到指定位置的前一个节点

}

if (!temp) {

std::cout << "Position out of bounds." << std::endl;

delete newNode; // 删除创建的节点，防止内存泄漏

return;

}

newNode->next = temp->next; // 新节点指向当前位置的下一个节点

temp->next = newNode; // 前一个节点指向新节点

}

删除头部节点
1. 删除链表的第一个节点

void deleteHead(Node*& head) {

if (!head) {

std::cout << "List is empty." << std::endl;

return;

}

Node* temp = head;

head = head->next; // 更新头节点

delete temp; // 删除原头节点

}

删除尾部节点
1. 删除链表的最后一个节点

void deleteTail(Node*& head) {

if (!head) {

std::cout << "List is empty." << std::endl;

return;

}

if (!head->next) { // 只有一个节点的情况

delete head;

head = nullptr;

return;

}

Node* temp = head;

while (temp->next->next) { // 找到倒数第二个节点

temp = temp->next;

}

delete temp->next; // 删除尾节点

temp->next = nullptr;

}

删除指定位置的节点
1. 删除链表中的指定位置（索引）的节点

void deleteAtPosition(Node*& head, int position) {

if (!head) {

std::cout << "List is empty." << std::endl;

return;

}

if (position == 0) { // 删除头节点

deleteHead(head);

return;

}

Node* temp = head;

for (int i = 0; i < position - 1 && temp; ++i) {

temp = temp->next; // 找到指定位置的前一个节点

}

if (!temp || !temp->next) {

std::cout << "Position out of bounds." << std::endl;

return;

}

Node* nodeToDelete = temp->next;

temp->next = temp->next->next; // 跳过要删除的节点

delete nodeToDelete; // 删除目标节点

}

查找操作
1. 查找链表中是否包含某个值，返回该值第一次出现的索引位置

int search(Node* head, int value) {

int index = 0;

Node* temp = head;

while (temp) {

if (temp->data == value) {

return index; // 找到目标值

}

temp = temp->next;

++index;

}

return -1; // 未找到返回 -1

}

遍历操作
1. 遍历并打印链表中的所有节点

void printList(Node* head) {

Node* temp = head;

while (temp) {

std::cout << temp->data << " -> ";

temp = temp->next;

}

std::cout << "nullptr" << std::endl;

}

销毁链表
1. 删除链表中的所有节点，释放内存

void clearList(Node*& head) {

while (head) {

deleteHead(head); // 不断删除头节点，直到链表为空

}

单链表其他操作

反转单链表
1. 迭代法

void reverseList(Node*& head) {

Node* prev = nullptr; // 前一个节点，初始为 nullptr

Node* curr = head; // 当前节点，从头节点开始

Node* next = nullptr; // 下一个节点

while (curr) {

next = curr->next; // 保存下一个节点

curr->next = prev; // 反转指针方向

prev = curr; // 前节点前移

curr = next; // 当前节点前移

}

head = prev; // 更新头节点为原来的尾节点

}

检测单链表是否有环
1. 该方法使用两个指针：一个慢指针每次走一步，快指针每次走两步
2. 如果链表中有环，两个指针最终会相遇；如果没有环，快指针会到达链表的末尾

bool hasCycle(Node* head) {

Node* slow = head; // 慢指针

Node* fast = head; // 快指针

while (fast && fast->next) {

slow = slow->next; // 慢指针每次走一步

fast = fast->next->next; // 快指针每次走两步

if (slow == fast) { // 快慢指针相遇，表示有环

return true;

}

return false; // 快指针到达链表末尾，无环

}

合并两个有序链表
1. 合并两个有序链表，使结果链表仍然保持有序

Node* mergeTwoLists(Node* l1, Node* l2) {

Node dummy(0); // 哨兵节点，帮助简化操作

Node* tail = &dummy;

while (l1 && l2) {

if (l1->data < l2->data) {

tail->next = l1;

l1 = l1->next;

} else {

tail->next = l2;

l2 = l2->next;

}

tail = tail->next;

}

// 连接剩余的节点

tail->next = l1 ? l1 : l2;

return dummy.next;

}

找到单链表的中间节点
1. 使用快慢指针找到链表的中间节点

Node* findMiddle(Node* head) {

Node* slow = head;

Node* fast = head;

while (fast && fast->next) {

slow = slow->next;

fast = fast->next->next;

}

return slow; // 当快指针到达末尾时，慢指针在中间

}

单链表归并排序
1. 单链表的插入排序时间复杂度为n^2
2. 归并排序的时间复杂度为n log n

struct Node {

int data;

Node* next;

Node(int val) : data(val), next(nullptr) {}

};

// 使用快慢指针找到链表的中间节点并拆分链表

Node* getMiddle(Node* head) {

if (!head || !head->next) {

return head;

}

Node* slow = head;

Node* fast = head->next;

while (fast && fast->next) {

slow = slow->next;

fast = fast->next->next;

}

Node* middle = slow->next;

slow->next = nullptr; // 拆分链表

return middle;

}

// 合并两个有序链表

Node* merge(Node* l1, Node* l2) {

Node dummy(0); // 创建一个哨兵节点，帮助合并链表

Node* tail = &dummy;

while (l1 && l2) {

if (l1->data < l2->data) {

tail->next = l1;

l1 = l1->next;

} else {

tail->next = l2;

l2 = l2->next;

}

tail = tail->next;

}

tail->next = l1 ? l1 : l2; // 连接剩余部分

return dummy.next;

}

// 归并排序

Node* mergeSort(Node* head) {

if (!head || !head->next) {

return head;

}

// 拆分链表

Node* middle = getMiddle(head);

Node* left = mergeSort(head);

Node* right = mergeSort(middle);

// 合并排序后的链表

return merge(left, right);

}

双链表

概述

双链表是一种链表数据结构，其中每个节点不仅有一个指向下一个节点的指针（next），还有一个指向前一个节点的指针（prev）
这使得双链表在遍历、插入和删除操作上比单链表更加灵活

双链表的节点定义

// 双链表节点的定义

struct Node {

int data; // 数据域

Node* next; // 指向下一个节点的指针

Node* prev; // 指向前一个节点的指针

Node(int val) : data(val), next(nullptr), prev(nullptr) {} // 构造函数

};

双链表的基本操作

创建双链表

1	Node* head = nullptr; // 创建一个空链表

插入到头部（头插法）

void insertAtHead(Node*& head, int value) {

Node* newNode = new Node(value); // 创建新节点

newNode->next = head; // 新节点的 next 指向当前头节点

if (head) { // 如果头节点存在

head->prev = newNode; // 当前头节点的 prev 指向新节点

}

head = newNode; // 更新头节点为新节点

}

插入到尾部（尾插法）

void insertAtTail(Node*& head, int value) {

Node* newNode = new Node(value); // 创建新节点

if (!head) { // 如果链表为空

head = newNode; // 直接将新节点作为头节点

return;

}

Node* temp = head;

while (temp->next) { // 遍历找到尾节点

temp = temp->next;

}

temp->next = newNode; // 尾节点的 next 指向新节点

newNode->prev = temp; // 新节点的 prev 指向原尾节点

}

插入到指定位置
1. 在链表的指定位置（索引）插入一个节点，假设索引从 0 开始

void insertAtPosition(Node*& head, int position, int value) {

if (position == 0) { // 插入到头部

insertAtHead(head, value);

return;

}

Node* newNode = new Node(value);

Node* temp = head;

for (int i = 0; i < position - 1 && temp; ++i) {

temp = temp->next; // 遍历到指定位置的前一个节点

}

if (!temp) {

std::cout << "Position out of bounds." << std::endl;

delete newNode; // 删除创建的节点，防止内存泄漏

return;

}

newNode->next = temp->next; // 新节点指向当前位置的下一个节点

newNode->prev = temp; // 新节点的 prev 指向前一个节点

if (temp->next) { // 如果当前位置的下一个节点存在

temp->next->prev = newNode; // 下一个节点的 prev 指向新节点

}

temp->next = newNode; // 前一个节点指向新节点

}

删除头部节点
1. 删除链表的第一个节点

void deleteHead(Node*& head) {

if (!head) {

std::cout << "List is empty." << std::endl;

return;

}

Node* temp = head;

head = head->next; // 更新头节点

if (head) {

head->prev = nullptr; // 如果头节点不为空，更新新头节点的 prev

}

delete temp; // 删除原头节点

}

删除尾部节点
1. 删除链表的最后一个节点

void deleteTail(Node*& head) {

if (!head) {

std::cout << "List is empty." << std::endl;

return;

}

if (!head->next) { // 只有一个节点的情况

delete head;

head = nullptr;

return;

}

Node* temp = head;

while (temp->next) { // 找到尾节点

temp = temp->next;

}

temp->prev->next = nullptr; // 倒数第二个节点的 next 置空

delete temp; // 删除尾节点

}

删除指定位置的节点
1. 删除链表中的指定位置（索引）的节点

void deleteAtPosition(Node*& head, int position) {

if (!head) {

std::cout << "List is empty." << std::endl;

return;

}

if (position == 0) { // 删除头节点

deleteHead(head);

return;

}

Node* temp = head;

for (int i = 0; i < position && temp; ++i) {

temp = temp->next; // 找到指定位置的节点

}

if (!temp) {

std::cout << "Position out of bounds." << std::endl;

return;

}

temp->prev->next = temp->next; // 前一个节点指向下一个节点

if (temp->next) {

temp->next->prev = temp->prev; // 下一个节点指向前一个节点

}

delete temp; // 删除目标节点

}

查找操作
1. 查找链表中是否包含某个值，返回该值第一次出现的索引位置

int search(Node* head, int value) {

int index = 0;

Node* temp = head;

while (temp) {

if (temp->data == value) {

return index; // 找到目标值

}

temp = temp->next;

++index;

}

return -1; // 未找到返回 -1

}

遍历操作

void printList(Node* head) {

Node* temp = head;

while (temp) {

std::cout << temp->data << " <-> ";

temp = temp->next;

}

std::cout << "nullptr" << std::endl;

}

反向遍历

void printReverse(Node* head) {

Node* temp = head;

if (!temp) return;

// 先找到尾节点

while (temp->next) {

temp = temp->next;

}

// 从尾节点开始反向遍历

while (temp) {

std::cout << temp->data << " <-> ";

temp = temp->prev;

}

std::cout << "nullptr" << std::endl;

}

销毁链表

void clearList(Node*& head) {

while (head) {

deleteHead(head); // 不断删除头节点，直到链表为空

}

双链表其他操作

反转双链表
1. 反转双链表是将链表的 next 和 prev 指针互换，使得链表的方向完全反转，即头节点变为尾节点，尾节点变为头节点

#include <iostream>

// 双链表节点的定义

struct Node {

int data;

Node* next;

Node* prev;

Node(int val) : data(val), next(nullptr), prev(nullptr) {}

};

// 插入节点到双链表的尾部

void insertAtTail(Node*& head, int value) {

Node* newNode = new Node(value); // 创建新节点

if (!head) { // 如果链表为空

head = newNode; // 将新节点作为头节点

return;

}

Node* temp = head;

while (temp->next) { // 找到尾节点

temp = temp->next;

}

temp->next = newNode; // 尾节点的 next 指向新节点

newNode->prev = temp; // 新节点的 prev 指向尾节点

}

// 打印链表

void printList(Node* head) {

Node* temp = head;

while (temp) {

std::cout << temp->data << " <-> ";

temp = temp->next;

}

std::cout << "nullptr" << std::endl;

}

// 反转双链表

void reverseDoublyLinkedList(Node*& head) {

Node* current = head;

Node* temp = nullptr;

// 遍历每个节点，交换 next 和 prev 指针

while (current) {

// 交换 next 和 prev 指针

temp = current->prev;

current->prev = current->next;

current->next = temp;

// 移动到下一个节点（即反转后原来的前一个节点）

current = current->prev;

}

// 更新头节点，新的头节点是原来的尾节点

if (temp) {

head = temp->prev;

}

检测是否有环

// 双链表节点的定义

struct Node {

int data;

Node* next;

Node* prev;

Node(int val) : data(val), next(nullptr), prev(nullptr) {}

};

// 检测双链表是否有环

bool hasCycle(Node* head) {

Node* slow = head; // 慢指针

Node* fast = head; // 快指针

while (fast && fast->next) {

slow = slow->next; // 慢指针走一步

fast = fast->next->next; // 快指针走两步

if (slow == fast) { // 快慢指针相遇，说明有环

return true;

}

return false; // 快指针到达链表末尾，无环

}

简单合并两个双链表

// 双链表节点的定义

struct Node {

int data;

Node* next;

Node* prev;

Node(int val) : data(val), next(nullptr), prev(nullptr) {}

};

// 插入节点到双链表的尾部

void insertAtTail(Node*& head, int value) {

Node* newNode = new Node(value);

if (!head) {

head = newNode;

return;

}

Node* temp = head;

while (temp->next) {

temp = temp->next;

}

temp->next = newNode;

newNode->prev = temp;

}

// 直接连接两个双链表

Node* concatenate(Node* l1, Node* l2) {

if (!l1) return l2; // 如果第一个链表为空，直接返回第二个链表

if (!l2) return l1; // 如果第二个链表为空，直接返回第一个链表

Node* tail = l1;

while (tail->next) { // 找到第一个链表的尾节点

tail = tail->next;

}

tail->next = l2; // 连接尾节点到第二个链表的头节点

l2->prev = tail; // 更新第二个链表头节点的 prev 指针

return l1; // 返回合并后的链表头节点

}

合并两个有序双链表

// 双链表节点的定义

struct Node {

int data;

Node* next;

Node* prev;

Node(int val) : data(val), next(nullptr), prev(nullptr) {}

};

// 插入节点到双链表的尾部

void insertAtTail(Node*& head, int value) {

Node* newNode = new Node(value);

if (!head) {

head = newNode;

return;

}

Node* temp = head;

while (temp->next) {

temp = temp->next;

}

temp->next = newNode;

newNode->prev = temp;

}

// 合并两个有序双链表

Node* mergeSortedLists(Node* l1, Node* l2) {

Node dummy(0); // 创建一个哨兵节点

Node* tail = &dummy; // 使用 tail 指针跟踪合并后的链表的末尾

// 合并两个链表，保持顺序

while (l1 && l2) {

if (l1->data < l2->data) {

tail->next = l1; // 将 l1 的当前节点连接到合并链表

l1->prev = tail; // 更新连接节点的前驱指针

l1 = l1->next; // 移动 l1 指针到下一个节点

} else {

tail->next = l2; // 将 l2 的当前节点连接到合并链表

l2->prev = tail; // 更新连接节点的前驱指针

l2 = l2->next; // 移动 l2 指针到下一个节点

}

tail = tail->next; // 更新合并链表的尾部指针

}

// 连接剩余的节点

if (l1) {

tail->next = l1;

l1->prev = tail;

} else if (l2) {

tail->next = l2;

l2->prev = tail;

}

return dummy.next; // 返回合并后的链表的第一个有效节点

}

找到双链表的中间节点

// 找到双链表的中间节点

Node* findMiddle(Node* head) {

if (!head) return nullptr;

Node* slow = head; // 慢指针

Node* fast = head; // 快指针

// 快指针每次移动两步，慢指针每次移动一步

while (fast && fast->next) {

slow = slow->next;

fast = fast->next->next;

}

return slow; // 慢指针到达中间位置

}

双链表归并排序

// 双链表节点的定义

struct Node {

int data;

Node* next;

Node* prev;

Node(int val) : data(val), next(nullptr), prev(nullptr) {}

};

// 使用快慢指针找到链表的中间节点并拆分链表

Node* getMiddle(Node* head) {

if (!head || !head->next) {

return head;

}

Node* slow = head;

Node* fast = head->next;

while (fast && fast->next) {

slow = slow->next;

fast = fast->next->next;

}

Node* middle = slow->next;

slow->next = nullptr; // 拆分链表

if (middle) {

middle->prev = nullptr;

}

return middle;

}

// 合并两个有序双链表

Node* merge(Node* left, Node* right) {

Node dummy(0); // 哨兵节点

Node* tail = &dummy;

while (left && right) {

if (left->data < right->data) {

tail->next = left;

left->prev = tail;

left = left->next;

} else {

tail->next = right;

right->prev = tail;

right = right->next;

}

tail = tail->next;

}

if (left) {

tail->next = left;

left->prev = tail;

} else if (right) {

tail->next = right;

right->prev = tail;

}

return dummy.next;

}

// 归并排序双链表

Node* mergeSort(Node* head) {

if (!head || !head->next) {

return head;

}

// 拆分链表

Node* middle = getMiddle(head);

Node* left = mergeSort(head);

Node* right = mergeSort(middle);

// 合并排序后的链表

return merge(left, right);

}

单链表
概述
单链表的节点定义
单链表的基本操作
单链表其他操作
双链表
概述
双链表的节点定义
双链表的基本操作
双链表其他操作

ds list

本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！

Bingliaolong 关注：0 粉丝：0 最后编辑于：2024-12-31

Everything will be better.

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

单链表

概述

单链表的节点定义

单链表的基本操作

单链表其他操作

双链表

概述

双链表的节点定义

双链表的基本操作

双链表其他操作

你可能也喜欢

热评文章

发表评论

标签云集