力扣热题100题解（c++）—链表

160.相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

    if (headA == nullptr || headB == nullptr) {return nullptr;}ListNode *ptrA = headA;ListNode *ptrB = headB;while (ptrA != ptrB) {// 如果 ptrA 移动到末尾，则移动到 headBptrA = (ptrA == nullptr) ? headB : ptrA->next;// 如果 ptrB 移动到末尾，则移动到 headAptrB = (ptrB == nullptr) ? headA : ptrB->next;}return ptrA; // 如果相交，返回相交节点；否则，返回 null

206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

    if (n == 0) return nullptr;ListNode* head = new ListNode(arr[0]);ListNode* current = head;for (int i = 1; i < n; i++) {current->next = new ListNode(arr[i]);current = current->next;}return head;

234.回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

    vector<int> values;ListNode* current = head;// 1. 将链表值存储到 vector 中while (current != nullptr) {values.push_back(current->val);current = current->next;}// 2. 双指针判断是否回文int left = 0;int right = values.size() - 1;while (left < right) {if (values[left] != values[right]) {return false;}left++;right--;}return true;

141.环形链表

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

    if (head == nullptr || head->next == nullptr) {return false; // 空链表或只有一个节点，肯定没有环}ListNode *slow = head;ListNode *fast = head->next; // 快指针从 head->next 开始，可以避免一开始就相遇while (fast != nullptr && fast->next != nullptr) {if (slow == fast) {return true; // 快慢指针相遇，说明有环}slow = slow->next;       // 慢指针移动一步fast = fast->next->next;  // 快指针移动两步}return false; // 快指针到达链表末尾，说明没有环

142.环形链表2

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。

 // 查找链表入环的第一个节点ListNode* detectCycle(ListNode *head) 
{if (head == nullptr || head->next == nullptr) {return nullptr; // 空链表或只有一个节点，无环}ListNode *slow = head;ListNode *fast = head;// 首先找到相遇点while (fast != nullptr && fast->next != nullptr) {slow = slow->next;           // 慢指针走一步fast = fast->next->next;     // 快指针走两步if (slow == fast) { // 找到相遇点// 从相遇点开始，另一个指针从头节点开始ListNode *entry = head;while (entry != slow) {entry = entry->next; // 从头节点开始slow = slow->next;    // 从相遇点开始}return entry; // 入环的第一个节点}}return nullptr; // 无环
}

21.合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    // 创建哑节点ListNode* dummy = new ListNode();ListNode* current = dummy;while (list1 != nullptr && list2 != nullptr) {if (list1->val <= list2->val) {current->next = list1;list1 = list1->next;} else {current->next = list2;list2 = list2->next;}current = current->next;}// 处理剩余节点if (list1 != nullptr) {current->next = list1;} else {current->next = list2;}return dummy->next; // 返回新链表的头节点

2.两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

    ListNode* dummyHead = new ListNode(0); // 哨兵节点方便处理ListNode* current = dummyHead;int carry = 0;while (l1 != nullptr || l2 != nullptr) {int x = (l1 != nullptr) ? l1->val : 0;int y = (l2 != nullptr) ? l2->val : 0;int sum = x + y + carry;carry = sum / 10;current->next = new ListNode(sum % 10);current = current->next;if (l1 != nullptr) l1 = l1->next;if (l2 != nullptr) l2 = l2->next;}if (carry > 0) {current->next = new ListNode(carry);}return dummyHead->next;

19.删除链表的倒数第N个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

    ListNode* dummyHead = new ListNode(0);dummyHead->next = head;  // 哑节点指向头节点ListNode* fast = dummyHead;ListNode* slow = dummyHead;// 快指针先走 n 步for (int i = 0; i < n; ++i) {if (fast == nullptr) {  // 处理 n 大于链表长度的情况return head;  // 或者抛出异常：throw std::invalid_argument("n is greater than the list length");}fast = fast->next;}// 同时移动快慢指针，直到快指针到达末尾while (fast != nullptr && fast->next != nullptr) {fast = fast->next;slow = slow->next;}// 删除节点slow->next = slow->next->next;return dummyHead->next;

24.两两交换链表中的结点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

    ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* prev = dummyHead;while (head != nullptr && head->next != nullptr) {ListNode* first = head;ListNode* second = head->next;prev->next = second;first->next = second->next;second->next = first;prev = first;head = first->next;}return dummyHead->next;

138.随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

    if (head == nullptr) {return nullptr;}// 1. 创建哈希表：原节点 -> 新节点unordered_map<Node*, Node*> nodeMap;// 2. 第一次遍历：创建新节点，建立映射关系Node* current = head;while (current != nullptr) {nodeMap[current] = new Node(current->val);current = current->next;}// 3. 第二次遍历：设置新节点的 next 和 random 指针current = head;while (current != nullptr) {nodeMap[current]->next = (current->next != nullptr) ? nodeMap[current->next] : nullptr;nodeMap[current]->random = (current->random != nullptr) ? nodeMap[current->random] : nullptr;current = current->next;}// 4. 返回新链表的头节点return nodeMap[head];

148.排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

    if (head == nullptr || head->next == nullptr) {return head; // 空链表或者只有一个节点的链表，直接返回}// 1. 分割链表：找到链表的中间节点ListNode* middle = findMiddle(head);ListNode* nextToMiddle = middle->next;middle->next = nullptr; // 断开链表，分割成两个子链表// 2. 递归排序：对两个子链表进行递归排序ListNode* left = sortList(head);ListNode* right = sortList(nextToMiddle);// 3. 合并链表：合并两个已排序的子链表return merge(left, right);}private:// 寻找链表的中间节点（快慢指针法）ListNode* findMiddle(ListNode* head) {ListNode* slow = head;ListNode* fast = head->next;  // Fast从 head->next 开始，使得偶数节点时，middle指向前半部分的最后一个节点while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;}return slow;}// 合并两个已排序的链表ListNode* merge(ListNode* list1, ListNode* list2) {ListNode dummyHead(0); // 使用哑节点简化操作ListNode* tail = &dummyHead;while (list1 != nullptr && list2 != nullptr) {if (list1->val < list2->val) {tail->next = list1;list1 = list1->next;} else {tail->next = list2;list2 = list2->next;}tail = tail->next;}// 将剩余的链表添加到尾部if (list1 != nullptr) {tail->next = list1;} else {tail->next = list2;}return dummyHead.next;

146.LRU缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

class LRUCache 
{
private:int capacity;std::unordered_map<int, int> cache; // 存储 key-value 对std::list<int> lruList;               // 维护 key 的访问顺序 (最近访问的在前面)std::unordered_map<int, std::list<int>::iterator> position; // 存储 key 在 lruList 中的位置
public:LRUCache(int capacity) : capacity(capacity){}int get(int key) {if (cache.find(key) == cache.end()) {return -1; // Key 不存在}// 将 key 移到链表头部，表示最近使用lruList.erase(position[key]);lruList.push_front(key);position[key] = lruList.begin(); // 更新 key 在链表中的位置return cache[key];}void put(int key, int value) {if (cache.find(key) != cache.end()) {// Key 已经存在，更新 value 并移到链表头部cache[key] = value;lruList.erase(position[key]);lruList.push_front(key);position[key] = lruList.begin();} else {// Key 不存在if (cache.size() == capacity) {// 缓存已满，移除最久未使用的元素int lruKey = lruList.back(); // 链表尾部是最近最少使用的 keycache.erase(lruKey);        // 从哈希表中移除position.erase(lruKey);     // 从位置映射中移除lruList.pop_back();          // 从链表中移除}// 插入新的 key-value 对cache[key] = value;lruList.push_front(key);        // 插入到链表头部position[key] = lruList.begin(); // 记录 key 在链表中的位置}}
};

链表定义

链表是有一系列结点组成的，每个结点包括两个部分：

1、存储数据元素的数据域；

2、存储下一个节点地址的指针域。

//单链表
struct ListNode 
{int data;               // 节点数据ListNode* next;        // 指向下一个节点的指针// 构造函数ListNode(int val) : data(val), next(nullptr) {}
};
//双链表
struct DListNode 
{int data;                     // 节点数据DListNode* next;             // 指向下一个节点的指针DListNode* prev;             // 指向前一个节点的指针// 构造函数DListNode(int val) : data(val), next(nullptr), prev(nullptr) {}
};

基本操作

1.插入节点

    // 在链表头插入节点void insertAtHead(int val) {ListNode *newNode = new ListNode(val);newNode->next = head;head = newNode;}// 在链表尾插入节点void insertAtTail(int val) {ListNode *newNode = new ListNode(val);if (head == nullptr) {head = newNode;return;}ListNode *current = head;while (current->next != nullptr) {current = current->next;}current->next = newNode;}// 在指定位置插入节点 (pos 从 1 开始计数)void insertAtPosition(int val, int pos) {if (pos < 1) {std::cerr << "Invalid position!" << std::endl;return;}ListNode *newNode = new ListNode(val);if (pos == 1) {newNode->next = head;head = newNode;return;}ListNode *current = head;for (int i = 1; i < pos - 1 && current != nullptr; ++i) {current = current->next;}if (current == nullptr) {std::cerr << "Position out of range!" << std::endl;delete newNode; // 确保内存不泄漏return;}newNode->next = current->next;current->next = newNode;}

2.删除节点

    // 删除头节点void deleteAtHead() {if (head == nullptr) {std::cerr << "List is empty! Cannot delete from head." << std::endl;return;}ListNode *temp = head;head = head->next;delete temp;}// 删除尾节点void deleteAtTail() {if (head == nullptr) {std::cerr << "List is empty! Cannot delete from tail." << std::endl;return;}if (head->next == nullptr) { // 只有一个节点delete head;head = nullptr;return;}ListNode *current = head;while (current->next->next != nullptr) {current = current->next;}delete current->next;current->next = nullptr;}// 删除指定值的节点void deleteByValue(int val) {if (head == nullptr) {std::cerr << "List is empty! Cannot delete value " << val << "." << std::endl;return;}// 如果要删除的是头节点if (head->val == val) {deleteAtHead();return;}ListNode *current = head;while (current->next != nullptr && current->next->val != val) {current = current->next;}if (current->next == nullptr) {std::cerr << "Value " << val << " not found!" << std::endl;return;}ListNode *temp = current->next;current->next = current->next->next;delete temp;}// 删除指定位置的节点 (pos 从 1 开始计数)void deleteAtPosition(int pos) {if (pos < 1) {std::cerr << "Invalid position!" << std::endl;return;}if (pos == 1) {deleteAtHead();return;}ListNode *current = head;for (int i = 1; i < pos - 1 && current != nullptr; ++i) {current = current->next;}if (current == nullptr || current->next == nullptr) {std::cerr << "Position out of range!" << std::endl;return;}ListNode *temp = current->next;current->next = current->next->next;delete temp;}

3.反转链表

    // 反转链表方法void reverse() {ListNode *prev = nullptr;ListNode *current = head;while (current != nullptr) {ListNode *nextNode = current->next; // 暂存下一个节点current->next = prev;               // 反转当前节点指向prev = current;                     // prev前移到当前节点current = nextNode;                 // current后移到下一个节点}head = prev; // 最后prev为新的头节点}

4.倒数第x个节点

//遍历两次链表ListNode* findNthFromEnd(int n) {if (head == nullptr) {std::cerr << "List is empty!" << std::endl;return nullptr;}// 第一次遍历计算链表长度int length = 0;ListNode *current = head;while (current != nullptr) {length++;current = current->next;}// 计算目标节点的索引int targetIndex = length - n;if (targetIndex < 0) {std::cerr << "n is larger than the length of the list!" << std::endl;return nullptr;}// 第二次遍历找到倒数第 n 个节点current = head;for (int i = 0; i < targetIndex; i++) {current = current->next;}return current;}//快慢指针法
ListNode* findNthFromEnd(int n) 
{ListNode *fast = head;ListNode *slow = head;// 让 fast 指针先移动 n 步for (int i = 0; i < n; ++i) {if (fast == nullptr) {std::cerr << "n is larger than the length of the list!" << std::endl;return nullptr;}fast = fast->next;}// 然后同时移动 fast 和 slow 指针while (fast != nullptr) {slow = slow->next;fast = fast->next;}return slow; // slow 即为倒数第 n 个节点
}

5.是否有环

// 判断链表是否有环
bool hasCycle(ListNode *head) 
{if (head == nullptr || head->next == nullptr) {return false; // 空链表或只有一个节点，不可能有环}ListNode *slow = head;ListNode *fast = head->next;while (fast != nullptr && fast->next != nullptr) {if (slow == fast) {return true; // 快慢指针相遇，存在环}slow = slow->next;           // 慢指针走一步fast = fast->next->next;     // 快指针走两步}return false; // 快指针到达末尾，无环
}