一、链表的定义

链表是一种动态数据结果，内存分配不是在创建链表时一次性完成的，每添加一个节点，分配一次内存，由于没有闲置的内存，链表的空间效率高于数组

二、定义单向链表

struct ListNode
{int m_nValue;ListNode* m_pNext;
};
void AddToTail(ListNode** pHead, int value)
{ListNode* pNew = new listNode();pNew->m_nValue = value;pNew->m_pNext = nullptr;if (*pHead == nullptr){*pHead = pNew;}else{ListNode* pNode = *pHead;while (*pHead->m_pNext != nullptr)pNode = pNode->m_pNext;pNode->m_pNext = pNew;}
}

3. 删除链表中的一个元素

void RemoveNode(ListNode** pHead, int value)
{if (pHead == nullptr || *pHead == nullptr)//pHead是指向链表头节点的指针，*pHead是链表的头节点return;ListNode* pToBeDeleted = nullptr;//分成两种情况，头节点和其他节点if ((*pHead)->m_nValue == value)//如果头节点是要删除的目标{pToBeDeleted = *pHead;*pHead = (*pHead)->m_pNext;}else{ListNode* pNode = *pHead;while (pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue != value)pNode = pNode->m_pNext;if (pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue == value){pToBeDeleted = pNode->m_pNext;pNode->m_pNext = pNode->m_pNext->m_pNext;}}if (pToBeDeleted != nullptr){delete pToBeDeleted;pToBeDeleted = nullptr;}
}

4 从头到尾打印链表

1. 上面这段代码中设计到了结构体的知识，结构体以struct为关键字，结构体内部可以有多个变量和函数。结构体的定义结构如下

struct Person
{
int n_year;
string name;
void sayHellow()
{
定义内容;
}
};

2. ListNode** pHead
   两个**表示的是指向指针的指针

5 相交链表

5.1方法一

使用哈希表解决

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode *> visited;ListNode *temp = headA;while (temp != nullptr){visited.insert(temp);temp = temp->next;}temp = headB;while (temp != nullptr){if(visited.count(temp)){return temp;}temp = temp->next;}return nullptr;}
};

5.1.2代码中遇到的问题

1.哈希表的定义

unordered_set 无键值哈希表
unordered_map 有键值哈希表

2.哈希表的一些函数
1.插入元素：

insert(key, value)：向std::unordered_map中插入键值对(key, value)。
insert(value)：向std::unordered_set中插入元素value。

2.访问元素：

at(key)：以给定的key作为参数，在std::unordered_map中查找对应的值，并返回引用。
find(key)：在std::unordered_map中查找具有给定key的元素。如果找到，返回指向该元素的
迭代器；否则返回end()迭代器。
count(key)：在std::unordered_map中计算具有给定key的元素个数。当存在时，返回1，否则返回0。

3.删除元素：

erase(key)：从std::unordered_map中删除具有给定key的键值对。
erase(position)：从std::unordered_map或std::unordered_set中删除给定位置（迭代器）上的元素。
clear()：从std::unordered_map或std::unordered_set中删除所有元素。

4.迭代遍历：

使用auto关键字和range-based for循环遍历哈希表中的元素。
使用迭代器（如begin()和end()）进行循环访问。

5.2方法二

使用双指法,双指针法的时间复杂度为O(n)，空间复杂度为O(1)

class Solution{
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){ListNode *A = headA;ListNode *B = headB;while (A!=nullptr && B!=nullptr){A = A->next;B= B->next;}if (A ==nullptr) A = headB;if (B ==nullptr) B = headA;while (A!=nullptr && B!=nullptr){A = A->next;B= B->next;}if (A ==nullptr) A = headB;if (B ==nullptr) B = headA;while (A!=nullptr && B!=nullptr){if(A == B) return A;A = A->next;B= B->next;}return nullptr;}
};

5.2.1 遇到的问题

nullptr：在C++中，nullptr 是一个特殊的空指针常量，用于表示一个指针不指向任何有效的内存地址。它在C++11标准中引入，旨在取代以前使用的 NULL 或 0 来表示空指针

6.删除链表倒数第n个节点

题目：

6.1 方法一

运行两遍，第一遍读取链表长度，第二遍删除节点

class Solution{
public:ListNode* removeNthFromEnd(ListNode* head, int n){if (head==nullptr||head->next==nullptr) return nullptr;ListNode* A = head;int sum_count=0;while(A!=nullptr){A = A->next;sum_count = sum_count + 1;}int forward_count = sum_count - n;A = head;if(n==1)//删除尾节点{while (sum_count-->2){A = A->next;}ListNode* B = A->next;A->next = nullptr;delete B;}else if(sum_count==n)//删除头节点{ListNode* B = A;head = head->next;delete B;}else//删除中间节点{while (forward_count-->1){A = A->next;}ListNode* B = A->next;A->next = A->next->next;delete B;}return head;}
};

6.2 方法二

使用栈的形式，先入栈，然后弹栈，弹的第N个，即为要删除的节点

 class Solution{//栈的形式找节点public:ListNode* removeNthFromEnd(ListNode* head, int n){stack<ListNode*> stk;ListNode* dummy = new ListNode(0,head);ListNode *A = head;ListNode *B = dummy;while(dummy){  stk.push(dummy);dummy = dummy->next;}while(n-->0){stk.pop();}ListNode *prev = stk.top();A = prev->next;prev->next = prev->next->next;delete A;head = B->next;delete dummy;return head;}};

6.2.1 遇到的问题

栈的定义：
栈的定义使用std模板中的stack，stack中有一些函数

入栈：stk.push(dummy);
出栈：stk.pop();
读取栈顶元素：stk.top();

方法三 6.3

快慢指针

class Solution{//快慢指针
public:ListNode* removeNthFromEnd(ListNode* head, int n){ListNode* dummy = new ListNode(0, head);ListNode* Fast = head;ListNode* Low = dummy;for(int i = 0; i < n; ++i){Fast = Fast->next;}while(Fast){Fast = Fast->next;Low = Low->next;}Low->next = Low->next->next;ListNode* ans = dummy->next;delete dummy;return ans;}
};