留言灌水区 | 汇芳书院
ac4fun opened this issue · 2 comments
ac4fun commented
ac4fun commented
双向循环链表
/**
* Project: baselib
* File: doublylist.cpp
* Author: AC4Fun
* Date: 2023/12/17
* Time: 16:26
* Desc:双向循环链表
*/
#include <iostream>
struct DoublyListNode {
int val;
DoublyListNode *prev;
DoublyListNode *next;
DoublyListNode(int val) : val(val), prev(nullptr), next(nullptr) {}
};
// 双向循环链表
class DoublyCircularList {
public:
DoublyCircularList() {
head = new DoublyListNode(0);
tail = new DoublyListNode(0);
head->next = tail;
tail->prev = head;
head->prev = tail;
tail->next = head;
}
~DoublyCircularList() {
DoublyListNode *node = head->next;
while (node != tail) {
DoublyListNode *next = node->next;
delete node;
node = next;
}
delete head;
}
void insert(int val) {
DoublyListNode *node = new DoublyListNode(val);
node->next = tail;
node->prev = tail->prev;
tail->prev->next = node;
tail->prev = node;
}
bool remove(int val) {
DoublyListNode *node = head->next;
while (node != tail) {
if (node->val == val) {
// DoublyListNode* nextNode = node->next; // 保存下一个节点
node->prev->next = node->next;
node->next->prev = node->prev;
delete node;
// node = nextNode;
return true;
}
node = node->next;
}
return false;
}
void print() {
DoublyListNode* current = head->next;
while (current != tail) {
std::cout << current->val << " ";
current = current->next;
}
std::cout << std::endl;
}
private:
DoublyListNode *head;
DoublyListNode *tail;
};
int main() {
DoublyCircularList list;
// 插入元素
list.insert(1);
list.insert(2);
list.insert(3);
list.print();
// 尝试删除元素
if (list.remove(2)) {
std::cout << "Element 2 removed.\n";
list.print();
} else {
std::cout << "Element 2 not found.\n";
}
// 再次尝试删除同一个元素
if (list.remove(3)) {
std::cout << "Element 3 removed again.\n";
list.print();
list.remove(1);
list.print();
list.insert(10);
list.print();
} else {
std::cout << "Element 2 not found again.\n";
}
return 0;
}
ac4fun commented
单链表经典算法题
/**
* Project: baselib
* File: linkedlist.cpp
* Author: AC4Fun
* Date: 2023/12/17
* Time: 14:53
* Desc: 单链表和双向循环链表
*/
#include <iostream>
#include <initializer_list>
// 单链表节点定义
struct ListNode {
int val;
ListNode *next;
explicit ListNode(int x) : val(x), next(nullptr) {}
};
class SinglyLinkedList {
public:
SinglyLinkedList() {
head = new ListNode(0);
tail = head;
}
~SinglyLinkedList() {
ListNode* p = head;
while(p != nullptr){
ListNode* q = p;
p = p->next;
delete q;
}
}
void insert(int val) {
auto* node = new ListNode(val);
tail->next = node;
tail = node;
}
bool remove(int val) {
ListNode* prev = head;
ListNode* p = head->next;
while(p != nullptr){
if(p->val == val){
prev->next = p->next;
if (p->next == nullptr){
tail = prev;
}
delete p;
return true;
}
prev = p;
p = p->next;
}
return false;
}
ListNode* find(int val) {
ListNode* p = head->next;
while(p != nullptr){
if(p->val == val){
return p;
}
p = p->next;
}
return nullptr;
}
void print() {
ListNode* p = head->next;
while(p != nullptr){
std::cout << p->val << " ";
p = p->next;
}
std::cout << std::endl;
}
private:
ListNode* head; // 带头节点
ListNode* tail;
};
// 反转链表
ListNode* reverseList(ListNode* head) {
if(head == nullptr || head->next == nullptr)
return head;
ListNode* prev = nullptr;
ListNode* p = head;
ListNode* q = head->next;
while(p != nullptr){
p->next = prev;
prev = p;
p = q;
if(q != nullptr){
q = q->next;
}
}
return prev;
}
ListNode* creatList(const std::initializer_list<int>& vals) {
ListNode* head = nullptr;
ListNode* tail = nullptr;
for(auto val : vals){
if(head == nullptr){
head = tail = new ListNode(val);
}else{
tail->next = new ListNode(val);
tail = tail->next;
}
}
return head;
}
void printList(const ListNode* head) {
while(head != nullptr){
std::cout << head->val;
head = head->next;
}
std::cout << std::endl;
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* p = dummy;
while(l1 != nullptr && l2 != nullptr){
if(l1->val < l2->val){
p->next = l1;
l1 = l1->next;
}else{
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
if(l1 != nullptr){
p->next = l1;
}
if(l2 != nullptr){
p->next = l2;
}
ListNode* head = dummy->next;
// delete dummy;
return head;
}
ListNode* findMiddleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast != nullptr && fast->next != nullptr){
slow = slow->next;
fast = fast->next->next;
// if(fast == slow){
// break;
// }
}
return slow;
}
ListNode* deleteNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* q = dummy;
ListNode* p = dummy;
ListNode* prev = dummy;
while(n-- && q != nullptr){
q = q->next;
}
while(q != nullptr){
prev = p;
p = p->next;
q = q->next;
}
prev->next = p->next;
ListNode* newHead = dummy->next;
delete p;
return newHead;
}
// 判断单链表是否有环
bool hasCycle(ListNode* head){
ListNode* fast = head;
ListNode* slow = head;
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
if (fast == slow){
return true;
}
}
return false;
}
// 寻找单链表环的入口
ListNode* detectCycle(ListNode* head){
ListNode* fast = head;
ListNode* slow = head;
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
if (fast == slow){
ListNode* detect = head;
while(slow != detect){
slow = slow->next;
detect = detect->next;
}
break;
}
}
return slow;
}
int main() {
// 测试反转链表
ListNode* head = creatList({1, 2, 3, 4, 6, 41, 5});
printList(head);
head = reverseList(head);
printList(head);
// 测试合并两个有序链表
ListNode* l1 = creatList({});
ListNode* l2 = creatList({3, 4, 5, 6, 7});
printList(mergeTwoLists(l1, l2));
// 测试查找链表中间节点
ListNode* head2 = creatList({1, 2, 3, 4, 5});
printList(findMiddleNode(head2));
// 测试删除链表倒数第n个节点
ListNode* head3 = creatList({1, 2, 3, 4, 5});
printList(head3);
head3 = deleteNthFromEnd(head3, 6);
std::cout << "After deletion nth from End: ";
printList(head3);
// 测试单链表是否有环
ListNode* head4 = creatList({1, 2, 3, 4, 5});
printList(head4);
std::cout << "head4 hashCycle: " << hasCycle(head4) << std::endl;
head4->next->next->next->next = head4->next->next;
std::cout << "head4 hashCycle after add cycle: " << hasCycle(head4) << std::endl;
ListNode* point = detectCycle(head4);
std::cout << "cycle start point: " << point->val << std::endl;
head3 = deleteNthFromEnd(head3, 6);
std::cout << "After deletion nth from End: ";
printList(head3);
// 测试单向链表
SinglyLinkedList list;
// 插入元素
list.insert(1);
list.insert(2);
list.insert(3);
std::cout << "After insertion: ";
list.print();
// 删除元素
if (list.remove(2)) {
std::cout << "Element 2 removed.\n";
} else {
std::cout << "Element 2 not found.\n";
}
std::cout << "After removal of 2: ";
list.print();
// 再次尝试删除同一个元素
if (list.remove(2)) {
std::cout << "Element 2 removed again.\n";
} else {
std::cout << "Element 2 not found.\n";
}
std::cout << "Final list: ";
list.print();
// 查找元素
ListNode* found = list.find(30);
if (found) {
std::cout << "Element 30 found.\n";
} else {
std::cout << "Element 30 not found.\n";
}
return 0;
}