1.相交链表
思路分析（直接上双指针）：
- 初始化两个指针，分别指向两个链表的头节点 headA 和 headB
- 遍历两个链表，当指针到达链表的末尾时，将指针移动到另一个链表的头部
- 如果链表相交，两个指针会在相交节点相遇
- 如果没有相交，两个指针会在遍历完整个链表后都变成 None，最终返回 None。
具体实现代码（详解版）：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(!headA || !headB) return nullptr;//任意链表为空
ListNode *pA = headA;
ListNode *pB = headB;
//当指针相等时，表示找到了相交节点，或者两个指针都为nullptr
while(pA != pB){
//当指针到达末尾时，重定向到另一个链表的头部
pA = pA ? pA->next : headB;//不为空则指向下一个节点，为空指向另一个链表头
pB = pB ? pB->next : headA;
}
return pA;// 返回相交节点或 nullptr
}
};
2.反转链表
思路分析1（迭代法）：通过迭代的方法，我们可以使用三个指针来反转链表。
- 初始化三个指针：
- prev指向当前节点的前一个节点，初始化为nullptr；
- current指向当前节点，初始为头节点head；
- next用于保存当前节点的下一个节点，防止丢失。
- 遍历链表：
- 每一步中，保存当前节点的下一个节点；
- 将当前节点的next指针指向前一个节点
- 移动指针，继续反转
具体实现代码（详解版）：
/**
* 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* prev = nullptr; // 前一个节点
ListNode* current = head; // 当前节点
while (current) {
ListNode* next = current->next; // 保存下一个节点
current->next = prev; // 反转当前节点的指针
prev = current; // 移动 prev 到当前节点
current = next; // 移动到下一个节点
}
return prev; // prev 成为新的头节点
}
};
思路分析2（递归无敌法）：
- 递归基本情况：如果head为空或只有一个节点，直接返回head
- 递归步骤：反转后面的链表并将当前节点的 next 指针指向 head，同时将当前节点的 next 设置为 nullptr。
具体实现代码（详解版）：
/**
* 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) {
//链表为空或者只有一个元素
if(!head || !head -> next) return head;
//递归反转链表
ListNode* newHead = reverseList(head->next);
//反转当前指针
head->next->next = head;
head->next = nullptr;
return newHead;//返回新的头节点
}
};
3.回文链表
思路分析1(赋值+头尾比较）
- 遍历链表，将每个节点的值存储到vals中；
- 比较元素
- 使用两个指针i和j，分别指向vals数组的开始和结束，在for循环中，依次比较vals[i]和vals[j]的值
- 如果发现任何不相等的元素，立即返回false，说明链表不是回文；
- 如果所有元素都匹配，返回true，说明链表是回文。
具体实现代码（详解版）：
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> vals; // 用于存储链表中的节点值
// 1. 遍历链表并将节点值存储到数组中
while (head != nullptr) {
vals.emplace_back(head->val); // 将当前节点值加入数组
head = head->next; // 移动到下一个节点
}
// 2. 比较数组的前半部分和后半部分
for (int i = 0, j = (int)vals.size() - 1; i < j; ++i, --j) {
if (vals[i] != vals[j]) {
return false; // 如果不相等，则不是回文
}
}
return true; // 所有值都匹配，则是回文链表
}
};
思路分析2（使用栈）：利用栈的特性来存储链表的前半部分，然后在遍历后半部分时与栈中的值进行比较
具体实现代码（详解版）：
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head || !head->next) {
return true; // 空链表或只有一个节点是回文
}
std::stack<int> s;
ListNode* current = head;
// 1. 将前半部分的节点值压入栈中
while (current) {
s.push(current->val);
current = current->next;
}
// 2. 比较栈中的值与链表中的值
current = head;
while (current) {
if (s.top() != current->val) {
return false;
}
s.pop();
current = current->next;
}
return true; // 如果所有值都匹配，则是回文链表
}
};
以上两种方法的时间复杂度和空间复杂度都是 O ( n ) . O(n). O(n).下面利用快慢指针法，以空间复杂度 O ( 1 ) O(1) O(1)实现回文链表的判断。
思路分析3（快慢指针）：
- 使用快慢指针找到链表的中间节点：快指针 fast 每次移动两个节点，慢指针 slow 每次移动一个节点。当快指针到达链表末尾时，慢指针位于链表的中间位置
- 反转链表的后半部分：从中间节点开始，反转后半部分的链表，使其变为从尾部到中间的逆序链表。
- 比较前半部分和反转后的后半部分：用两个指针从头部和反转后的中间开始向后比较，若有不相等的值则不是回文链表。
具体实现代码（详解版）：
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(!head || !head->next) return true;
//1.使用快慢指针找到中间节点
ListNode *slow = head,*fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
//2.反转后半部分链表
ListNode *prev = nullptr;
while(slow){
ListNode *nextNode = slow->next;
slow->next = prev;
prev = slow;
slow = nextNode;
}
//比较前半部分和反转后的后半部分
ListNode *left = head;
ListNode *right = prev;//prev现在是反转后的链表头
while(right){//只需比较后半部分的节点数
if(left->val != right->val) return false;
left = left->next;
right = right->next;
}
return true;//如果没有发现不相等的节点，则回文链表
}
};
4.环形列表
思路分析1（哈希表）：我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。
具体实现代码(详解版）：
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> visited;
while (head != nullptr) {
// 检查当前节点是否已访问过
if (visited.count(head)) {
return true; // 存在环
}
visited.insert(head); // 将当前节点标记为已访问
head = head->next;
}
return false; // 没有环
}
};
思路分析2（快慢指针）：
- 快慢指针：slow 每次前进一步，而 fast 每次前进两步。如果 fast 和 slow 在某一时刻相遇，说明链表有环。
- 退出条件：如果 fast 或 fast->next 为 nullptr，则链表没有环。
- 这样实现的时间复杂度为 O(n)，空间复杂度为 O(1)，是判断链表是否有环的标准解法。
class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head || !head->next) return false;
ListNode *slow = head;
ListNode *fast = head->next;
while (fast != slow) {
if (!fast || !fast->next) return false;
slow = slow->next;
fast = fast->next->next;
}
return true; // fast和slow相遇表示有环
}
};
![[A-14]ARMv8/ARMv9-Memory-内存模型的类型(Device Normal)](https://i-blog.csdnimg.cn/direct/a66d742948644d7ca4667873a59a53aa.png#pic_center)