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 移动到末尾，则移动到 headB
        ptrA = (ptrA == nullptr) ? headB : ptrA->next;

        // 如果 ptrB 移动到末尾，则移动到 headA
        ptrB = (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(); // 链表尾部是最近最少使用的 key
                cache.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; // 快指针到达末尾，无环
}