（用于复习）

目录

线性表

顺序表

链表

单链表

单向 \ 双向

带哨兵位 \ 不带哨兵位

循环 \ 非循环

无头单向非循环链表实现

oj题

203. 移除链表元素

206. 反转链表

快慢指针

141.环形链表

【解题思路】

带头双向循环链表

顺序表和链表的区别

---

线性表

        常见的线性表：顺序表、链表、栈、队列、字符串...。

• 逻辑上： 线性结构
• 物理上： 不一定是连续

顺序表

#include <iostream>
#include <cassert>
#include <malloc.h>
#include <cstdlib>namespace qcr_vector
{typedef int VectorType;struct Vector{VectorType* _array;  // 指向动态开辟的数组uint64_t _size;        // 有效数据个数uint64_t _capacity;    // 容量空间的大小};/****************** 顺序表初始化*****************/void VectorInit(Vector* vector){assert(vector);vector->_array = nullptr;vector->_capacity = vector->_size = 0;}/****************** 检查空间，如果满了，进行增容*****************/void VectorCapacity(Vector* vector){assert(vector);if(vector->_capacity == vector->_size){uint64_t new_capacity = vector->_capacity == 0 ? 5 : vector->_capacity * 2;VectorType* tmp = (VectorType*)realloc(vector->_array, new_capacity * sizeof(VectorType));if(tmp == nullptr){perror("VectorCapacity::realloc");exit(-1);}vector->_array = tmp;vector->_capacity = new_capacity;}}// 顺序表在pos位置插入elementvoid VectorInsert(Vector *vector, uint64_t pos, VectorType element){assert(vector);assert(pos < vector->_size);VectorCapacity(vector);for(int i = vector->_size; i > pos; i--){vector->_array[i] = vector->_array[i - 1];}vector->_array[pos] = element;(vector->_size)++;}// 顺序表删除pos位置的值void VectorErase(Vector *vector, uint64_t pos){assert(vector);assert(pos < vector->_size);for(int i = pos; i < vector->_size - 1; i--){vector->_array[i] = vector->_array[i + 1];}(vector->_size)--;}// 顺序表尾插void VectorPushBack(Vector* vector, VectorType element){VectorInsert(vector, vector->_size, element);// assert(vector);// VectorCapacity(vector);// vector->_array[vector->_size] = element;// (vector->_size)++;}// 顺序表尾删void VectorPopBack(Vector* vector){VectorErase(vector, vector->_size - 1);// assert(vector);// (vector->_size)--;}// 顺序表头插void VectorPushFront(Vector* vector, VectorType element){VectorInsert(vector, 0, element);// assert(vector);// VectorCapacity(vector);// for(int i = vector->_size; i > 0; i--)// {//     vector->_array[i] = vector->_array[i - 1];// }// vector->_array[0] = element;// (vector->_size)++;}// 顺序表头删void VectorPopFront(Vector* vector){VectorErase(vector, 0);// assert(vector);// for(int i = 0; i < vector->_size - 1; i--)// {//     vector->_array[i] = vector->_array[i + 1];// }// (vector->_size)--;}// 顺序表查找int64_t VectorFind(Vector *vector, VectorType element){assert(vector);for(int i = 0; i < vector->_size; i++){if(vector->_array[i] == element){return i;}}return -1;}// 顺序表销毁void VectorDestory(Vector *vector){assert(vector);vector->_size = vector->_capacity = 0;if(vector->_array)free(vector->_array);vector->_array = nullptr;}// 顺序表打印void VectorPrint(Vector *vector){assert(vector);for(uint64_t i = 0; i < vector->_size; i++){std::cout << vector->_array[i] << " ";}std::cout << std::endl;}
};

链表

单链表

单向 \ 双向

带哨兵位 \ 不带哨兵位

循环 \ 非循环

最常用还是两种结构:

• 无头单向非循环链表
• 带头双向循环链表

1. 无头单向非循环链表：一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。（笔试面试出现很多）
2. 带头双向循环链表：一般用在单独存储数据。

无头单向非循环链表实现

#include <iostream>
#include <cassert>namespace qcr_single_list
{typedef int SingleListType;struct SListNode{SingleListType _data;SListNode *_next;};/***************** 动态申请一个结点****************/SListNode *BuySListNode(SingleListType data){SListNode *single_list = (SListNode *)malloc(sizeof(SListNode));if (single_list == nullptr){perror("BuySListNode::malloc");exit(-1);}single_list->_data = data;single_list->_next = nullptr;return single_list;}/***************** 单链表在pos位置之后插入data****************/void SListInsertAfter(SListNode *pos, SingleListType data){assert(pos);SListNode *single_list = BuySListNode(data);single_list->_next = pos->_next;pos->_next = single_list;}/***************** 单链表删除pos位置之后的值****************/void SListEraseAfter(SListNode *pos){assert(pos);assert(pos->_next);SListNode *erase = pos->_next;pos->_next = pos->_next->_next;free(erase);}/***************** 单链表头插****************/void SListPushFront(SListNode **single_list, SingleListType data){SListNode *new_SListNode = BuySListNode(data);new_SListNode->_next = (*single_list);*single_list = new_SListNode;}/***************** 单链表尾插****************/void SListPushBack(SListNode **single_list, SingleListType data){SListNode *new_SListNode = BuySListNode(data);if (*single_list) // 尾插{SListNode *cur = *single_list;while (cur->_next){cur = cur->_next;}cur->_next = new_SListNode;}else // 头插{*single_list = new_SListNode;}}/***************** 单链表头删****************/void SListPopFront(SListNode **single_list){assert(*single_list);SListNode *erase = *single_list;*single_list = (*single_list)->_next;free(erase);}/***************** 单链表尾删****************/void SListPopBack(SListNode **single_list){assert(*single_list);if (nullptr == (*single_list)->_next){free(*single_list);*single_list = nullptr;}else{SListNode* cur = *single_list;while (cur->_next->_next){cur = cur->_next;}SListNode *erase = cur->_next;cur->_next = nullptr;free(erase);}}/***************** 单链表查找****************/SListNode *SListFind(SListNode *single_list, SingleListType data){assert(single_list);SListNode *cur = single_list;while (cur){if (cur->_data == data)return cur;cur = cur->_next;}return nullptr;}/***************** 单链表打印****************/void SListPrint(SListNode *single_list){SListNode *cur = single_list;while (cur != nullptr){printf("%d->", cur->_data);cur = cur->_next;}printf("nullptr\n");}/***************** 单链表销毁****************/void SListDestory(SListNode** single_list){assert(*single_list);SListNode* cur = *single_list;while (cur){SListNode* next = cur->_next;free(cur);cur = _next;}*single_list = nullptr;}
}

oj题

203. 移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

---

/*** 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* cur = head;ListNode* prev = nullptr;while(cur){if(cur->val == val){if(prev == nullptr){head = head->next;cur = head;}else{prev->next = cur->next;cur = cur->next;}}else{prev = cur;cur = cur->next;}}return head;}
};

206. 反转链表

206. 反转链表 - 力扣（LeetCode）

---

/*** 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* ret = nullptr;ListNode* cur = head;while(cur){ListNode* next = cur->next;cur->next = ret;ret = cur;cur = next;}return ret;}
};

链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
 

---

        双指针实现。

易错：
        两个临界需要全部关注到。

• 1,{1,2,3,4,5}
• 5,{1,2,3,4,5}

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
#include <asm-generic/errno.h>
class Solution {
public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {ListNode* cur = pListHead;while(k--){if(cur)cur = cur->next;elsereturn nullptr;}ListNode* prev = pListHead;while(cur){cur = cur->next;prev = prev->next;}return prev;}
};

(链表OJ题一定要确定边界，防止使用nullptr指针)

快慢指针

141.环形链表

141. 环形链表 - 力扣（LeetCode）

---

【解题思路】

带头双向循环链表

#include <iostream>
#include <malloc.h>
#include <cassert>namespace qcr_list
{typedef int ListDataList;struct ListNode{ListDataList _data;ListNode* _next;ListNode* _prev;};// 带头+双向+循环链表增删查改实现ListNode* Init(){ListNode* head_node = (ListNode*)malloc(sizeof(ListNode));head_node->_prev = head_node;head_node->_next = head_node;return head_node;} // 创建新结点ListNode* ListCreate(ListDataList data){ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));if(nullptr == new_node)perror("ListCreate::malloc");new_node->_data = data;new_node->_prev = new_node->_next = nullptr;return new_node;}// 双向链表尾插void ListPushBack(ListNode* pHead, ListDataList data){assert(pHead);ListNode* tail = pHead->_prev;ListNode* new_node = ListCreate(data);tail->_next = new_node;new_node->_next = pHead;new_node->_prev = tail;pHead->_prev = new_node;}   // 双向链表头插void ListPushFront(ListNode* pHead, ListDataList data){assert(pHead);ListNode* next = pHead->_next;ListNode* new_node = ListCreate(data);pHead->_next = new_node;new_node->_next = next;new_node->_prev = pHead;next->_prev = new_node;}// 双向链表尾删void ListPopBack(ListNode* pHead){assert(pHead);if(pHead->_next == pHead)return;ListNode* erase = pHead->_prev;erase->_prev->_next = pHead;pHead->_prev = erase->_prev;erase->_next = erase->_prev = nullptr;free(erase);erase = nullptr;}// 双向链表头删void ListPopFront(ListNode* pHead){assert(pHead);if(pHead->_next == pHead)return;ListNode* erase = pHead->_next;erase->_next->_prev = pHead;pHead->_next = erase->_next;erase->_next = erase->_prev = nullptr;free(erase);erase = nullptr;}// 双向链表插入void ListInsert(ListNode* pos, ListDataList data){assert(pos);ListNode* new_node = ListCreate(data);ListNode* prev = pos->_prev;prev->_next = new_node;new_node->_next = pos;new_node->_prev = prev;pos->_prev = new_node;}// 双向链表删除void ListErase(ListNode* pos){assert(pos);ListNode* prev = pos->_prev;ListNode* next = pos->_next;pos->_next = pos->_prev = nullptr;free(pos);pos = nullptr;prev->_next = next;next->_prev = prev;}// 双向链表打印void ListPrint(ListNode* pHead){assert(pHead);ListNode* cur = pHead->_next;while(pHead != cur){std::cout << cur->_data << "->";cur = cur->_next;}std::cout << "nullptr" << std::endl;}// 双向链表查找ListNode* ListFind(ListNode* pHead, ListDataList data){assert(pHead);ListNode* cur = pHead->_next;while(pHead != cur){if(data == cur->_data){return cur;}cur = cur->_next;}return nullptr;}// 双向链表销毁void ListPrint(ListNode* pHead){assert(pHead);ListNode* cur = pHead;while(nullptr != cur){if(cur == pHead){cur->_prev->_next = nullptr;}ListNode* next = cur->_next;cur->_next = cur->_prev = nullptr;free(cur);cur = next;}}
}

顺序表和链表的区别

顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入 \ 删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低