7.链表文章目录7.链表160.相交链表方法一：c（暴力解法）方法一：js方法二：c（哈希）方法二：js方法三：c（双指针）方法三：js206.反转链表方法一：c++方法二：js234.回文链表方法一：c方法一：js方法二：c方法二：js方法三：c方法三：js141.环形链表方法一：c方法一：js方法二：c方法二：js142.环形链表 II方法一：c方法一：js方法二：c方法二：js21.合并两个有序链表方法一：c方法一：js2.两数相加方法一：c++方法二：c++方法三：c++方法四：c++19.删除链表的倒数第 N 个结点方法一：c方法一：js方法二：c方法二：js24.两两交换链表中的节点方法一：c方法一：js25.K 个一组翻转链表方法一：c++方法二：js138.随机链表的复制方法一：c方法一：js148.排序链表方法一：c方法一：js方法二：c方法二：js23.合并 K 个升序链表方法一：c方法一：js146.LRU 缓存方法一：js方法二：c方法二：js160.相交链表给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null图示两个链表在节点c1开始相交**：**题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须保持其原始结构。自定义评测：评测系统的输入如下（你设计的程序不适用此输入）：intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表listB- 第二个链表skipA- 在listA中（从头节点开始）跳到交叉节点的节点数skipB- 在listB中（从头节点开始）跳到交叉节点的节点数评测系统将根据这些输入创建链式数据结构，并将两个头节点headA和headB传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案。示例 1：输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。示例 2：输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Intersected at '2' 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。示例 3：输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：No intersection 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null方法一：c（暴力解法）简单的一个想法，对链表 A 中的每一个结点，我们都遍历一次链表 B 查找是否存在重复结点，第一个查找到的即第一个公共结点ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){for(ListNode*p=headA;p!=nullptr;p=p-next){for(ListNode*q=headB;q!=nullptr;q=q-next){if(p==q)returnp;}}returnnullptr;}方法一：js// 定义链表节点类，模拟 C++ 的 ListNode 结构体classListNode{constructor(val){this.val=val;this.next=null;}}// 转换后的核心函数：查找两个链表的相交节点functiongetIntersectionNode(headA,headB){// 外层循环遍历链表 A 的每个节点for(letp=headA;p!==null;p=p.next){// 内层循环遍历链表 B 的每个节点for(letq=headB;q!==null;q=q.next){// 判断节点是否是同一个引用（相交的核心：地址/引用相同）if(p===q){returnp;}}}// 没有相交节点时返回 nullreturnnull;}方法二：c（哈希）判断两个链表是否相交，可以使用哈希集合存储链表节点。首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：如果当前节点不在哈希集合中，则继续遍历下一个节点；如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都在两个链表的相交部分，因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点，返回该节点。如果链表 headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 null。structHashTable{structListNode*key;// 哈希表存储的键：链表节点的指针（地址）UT_hash_handle hh;// UT_hash 库必需的句柄，用于管理哈希表（无需手动操作）};// 核心函数：查找两个链表的相交节点，参数：headA-链表A头节点，headB-链表B头节点，返回值：相交节点指针（无则返回NULL）structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){structHashTable*hashTable=NULL;// 初始化哈希表指针为NULL（UT_hash 要求哈希表初始化为空）structListNode*temp=headA;// 定义临时指针temp，初始指向链表A的头节点，用于遍历链表Awhile(temp!=NULL){// 遍历链表A的所有节点，将每个节点的指针存入哈希表structHashTable*tmp;// 定义临时哈希表节点指针tmp，用于接收查找结果// HASH_FIND：在哈希表hashTable中查找键为temp的节点，参数：hh(句柄)、哈希表指针、查找键地址、键大小、接收结果指针HASH_FIND(hh,hashTable,temp,sizeof(structHashTable*),tmp);if(tmp==NULL){// 如果查找结果为NULL，说明该节点还未存入哈希表tmp=malloc(sizeof(structHashTable));// 为新的哈希表节点分配内存（大小为HashTable结构体）tmp-key=temp;// 将当前链表节点的指针赋值给哈希表节点的key字段// HASH_ADD：将新节点添加到哈希表，参数：hh(句柄)、哈希表指针、键字段名、键大小、要添加的节点HASH_ADD(hh,hashTable,key,sizeof(structHashTable*),tmp);}temp=temp-next;// temp指针后移，遍历链表A的下一个节点}temp=headB;// 重置temp指针，指向链表B的头节点，用于遍历链表Bwhile(temp!=NULL){// 遍历链表B的所有节点，检查当前节点是否存在于哈希表中structHashTable*tmp;// 定义临时哈希表节点指针tmp，用于接收查找结果HASH_FIND(hh,hashTable,temp,sizeof(structHashTable*),tmp);// 在哈希表中查找当前链表B节点的指针if(tmp!=NULL){// 如果查找结果不为NULL，说明该节点在链表A中存在（即相交节点）returntemp;// 返回该相交节点的指针}temp=temp-next;// temp指针后移，遍历链表B的下一个节点}returnNULL;// 遍历完链表B后未找到相交节点，返回NULL}方法二：jsvargetIntersectionNode=function(headA,headB){// 定义函数，参数为两个链表的头节点，返回相交节点（无则返回null）constvisited=newSet();// 创建空Set集合，用于存储链表A的节点引用（地址）lettemp=headA;// 声明临时指针temp，初始指向链表A的头节点while(temp!==null){// 循环遍历链表A，直到temp指向null（链表末尾）visited.add(temp);// 将当前链表A的节点添加到Set集合中temp=temp.next;// temp指针后移，指向链表A的下一个节点}temp=headB;// 重置temp指针，指向链表B的头节点while(temp!==null){// 循环遍历链表B，直到temp指向null（链表末尾）if(visited.has(temp)){// 检查当前链表B的节点是否存在于Set集合中（即是否在链表A中出现过）returntemp;// 找到相交节点，直接返回该节点}temp=temp.next;// temp指针后移，指向链表B的下一个节点}returnnull;// 遍历完链表B未找到相交节点，返回null};方法三：c（双指针）思路分析：一上来没看懂这题要做什么，看了题解才知道这题是要找到两个链表相交的首个公共节点，一个巧妙的解法就是用双指针，一个指针遍历完之后，指向另一条链表的头节点，这样相当于做了一个长度对齐。边界判断：先处理任一链表为空的情况，直接返回空；双指针核心：指针走到末尾就切换到另一个链表的头，保证总路程相等；循环退出条件：指针相遇（要么是相交节点，要么都是空），直接返回该指针即可。ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){if(headA==nullptr||headB==nullptr){// 边界条件：如果任一链表为空，直接返回空（无相交节点）returnnullptr;// 空链表不可能和其他链表相交，返回nullptr}ListNode*pA=headA,*pB=headB;// 初始化两个指针，pA指向链表A头节点，pB指向链表B头节点while(pA!=pB){// 循环条件：两个指针指向的节点不同时继续（相遇时退出）pA=pA==nullptr?headB:pA-next;// pA走到末尾（nullptr）则切换到链表B头节点，否则往后走一步pB=pB==nullptr?headA:pB-next;// pB走到末尾（nullptr）则切换到链表A头节点，否则往后走一步}returnpA;// 退出循环时pA==pB，要么是相交节点，要么都是nullptr（无相交）}方法三：jsvargetIntersectionNode=function(headA,headB){if(headA===null||headB===null){// 边界条件：如果任一链表为空，直接返回null（无相交节点）returnnull;// 空链表不可能和其他链表相交，返回null}letpA=headA,pB=headB;// 初始化两个指针，pA指向链表A头节点，pB指向链表B头节点while(pA!==pB){// 循环条件：两个指针指向的节点不同时继续（相遇时退出）pA=pA===null?headB:pA.next;// pA走到末尾（null）则切换到链表B头节点，否则往后走一步pB=pB===null?headA:pB.next;// pB走到末尾（null）则切换到链表A头节点，否则往后走一步}returnpA;// 退出循环时pA===pB，要么是相交节点，要么都是null（无相交）};206.反转链表给你单链表的头节点head，请你反转链表，并返回反转后的链表。示例 1：输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]示例 2：输入：head = [1,2] 输出：[2,1]示例 3：输入：head = [] 输出：[]方法一：c++#include iostream using namespace std; // 定义链表节点结构 struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; // 反转链表的函数 ListNode* reverseList(ListNode* head) { // cur 指向当前节点，初始化为链表头节点 // pre 指向当前节点的前一个节点，初始化为 nullptr ListNode *cur = head, *pre = nullptr; // 当 cur 不为空时，说明还没有遍历到链表的末尾 while (cur != nullptr) { // 保存 cur 的下一个节点，防止在修改 cur-next 后丢失后续链表的连接 ListNode* tmp = cur-next; // 将 cur 的 next 指针指向 pre，实现当前节点的指针反转 cur-next = pre; // 将 pre 移动到当前节点 cur 的位置，以便下一次迭代时 pre 指向当前节点的前一个节点 pre = cur; // 将 cur 移动到原来保存的下一个节点 tmp 的位置，继续处理下一个节点 cur = tmp; } // 当循环结束时，cur 为 nullptr，pre 指向的就是反转后的链表头节点，返回 pre return pre; } // 辅助函数，用于打印链表 void printList(ListNode* head) { while (head != nullptr) { cout head-val " "; head = head-next; } cout endl; } int main() { // 创建示例链表 [1,2,3,4,5] ListNode* head = new ListNode(1); ListNode* node2 = new ListNode(2); ListNode* node3 = new ListNode(3); ListNode* node4 = new ListNode(4); ListNode* node5 = new ListNode(5); head-next = node2; node2-next = node3; node3-next = node4; node4-next = node5; cout "输入链表: "; printList(head); // 调用反转链表函数 ListNode* reversedHead = reverseList(head); cout "输出链表: "; printList(reversedHead); // 释放链表节点内存 ListNode* current = reversedHead; while (current != nullptr) { ListNode* next = current-next; delete current; current = next; } return 0; }方法二：js// 定义链表节点类，每个节点包含一个值 val 和一个指向下一个节点的指针 nextclassListNode{constructor(val=0,next=null){this.val=val;this.next=next;}}// 反转链表的函数functionreverseList(head){// 初始化 prev 为 null，用于记录当前节点的前一个节点letprev=null;// 初始化 cur 为头节点，从链表头部开始处理letcur=head;// 只要 cur 不为 null，就继续处理链表节点while(cur!==null){// 保存当前节点的下一个节点，避免修改指针后丢失后续节点constnext=cur.next;// 将当前节点的 next 指针指向前一个节点，实现反转cur.next=prev;// 更新 prev 为当前节点，为下一次反转做准备prev=cur;// 更新 cur 为之前保存的下一个节点，继续处理后续节点cur=next;}// 当 cur 为 null 时，说明链表处理完毕，prev 即为反转后链表的头节点returnprev;}// 辅助函数，将数组转换为链表functionarrayToList(arr){if(arr.length===0)returnnull;// 创建头节点lethead=newListNode(arr[0]);letcurrent=head;// 遍历数组，依次创建节点并连接成链表for(leti=1;iarr.length;i++){current.next=newListNode(arr[i]);current=current.next;}returnhead;}// 辅助函数，将链表转换为数组，方便打印结果functionlistToArray(head){constresult=[];letcurrent=head;// 遍历链表，将节点值存入数组while(current){result.push(current.val);current=current.next;}returnresult;}constinputArray=[1,2,3,4,5];// 测试代码constinputList=arrayToList(inputArray);// 将输入数组转换为链表constreversedList=reverseList(inputList);// 调用反转链表函数constoutputArray=listToArray(reversedList);// 将反转后的链表转换为数组console.log("输入:",inputArray);console.log("输出:",outputArray);234.回文链表给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。示例 1：输入：head = [1,2,2,1] 输出：true示例 2：输入：head = [1,2] 输出：false方法一：c思路分析：回文链表是指向前和向后读都相同的链表，刚做完上题的反转链表，一个朴素的思想就是把链表先翻转一下，然后两个链表遍历对比，于是写了以下代码：class Solution{public:boolisPalindrome(ListNode*head){ListNode*curr=head;ListNode*prev=nullptr;ListNode*next;while(curr){next=curr-next;curr-next=prev;prev=curr;curr=next;}while(head){if(prev-val!=head-val)returnfalse;prev=prev-next;head=head-next;}returntrue;}};上面这个代码无法通过，因为犯了一个错误，*curr = head 并没有复制链表，而是使 curr 和 head 指向了同一个链表（地址相同）。因此，要复制链表，需要单独 new 一个 ListNode，再遍历复制。ListNode*cloneList(ListNode*head){if(!head)returnnullptr;ListNode*newHead=newListNode(head-val);ListNode*tail=newHead;head=head-next;while(head){tail-next=newListNode(head-val);tail=tail-next;head=head-next;}returnnewHead;}class Solution{public:boolisPalindrome(ListNode*head){ListNode*copy=cloneList(head);// 原地反转 copyListNode*curr=copy;ListNode*prev=nullptr;ListNode*next;while(curr){next=curr-next;curr-next=prev;prev=curr;curr=next;}// 和 head 比较while(head){if(prev-val!=head-val)returnfalse;prev=prev-next;head=head-next;}returntrue;}};方法一：js// 定义链表节点类（JS 无原生链表，需手动实现）classListNode{constructor(val){this.val=val;this.next=null;}}// 克隆链表的函数（对应 C++ 的 cloneList 函数）functioncloneList(head){if(!head)returnnull;// 边界条件：空链表直接返回nullconstnewHead=newListNode(head.val);// 创建新链表头节点，值和原链表头一致lettail=newHead;// 尾指针，用于构建新链表head=head.next;// 原链表指针后移，开始遍历剩余节点while(head){// 遍历原链表所有节点tail.next=newListNode(head.val);// 新建节点并挂载到新链表尾部tail=tail.next;// 尾指针后移head=head.next;// 原链表指针后移}returnnewHead;// 返回克隆后的新链表头节点}// 核心逻辑：判断链表是否为回文链表varisPalindrome=function(head){constcopy=cloneList(head);// 克隆原链表，避免修改原链表// 原地反转克隆后的链表（对应 C++ 的反转逻辑）letcurr=copy;// 当前遍历节点，初始指向克隆链表头letprev=null;// 前驱节点，初始为nullletnext;// 临时存储下一个节点while(curr){next=curr.next;// 先保存当前节点的下一个节点（防止断链）curr.next=prev;// 反转当前节点的指针，指向前驱节点prev=curr;// 前驱节点后移到当前节点curr=next;// 当前节点后移到之前保存的下一个节点}// 比较原链表和反转后的克隆链表是否完全一致while(head){if(prev.val!==head.val){// 只要有一个节点值不同，就不是回文returnfalse;}prev=prev.next;// 反转链表指针后移head=head.next;// 原链表指针后移}returntrue;// 所有节点值都匹配，是回文链表};方法二：c这样做拷贝显然过于复杂，一个更好的思路是将链表转换成数组，因为数组更方便查询。转换成数组后，就可以通过双指针的思路，往中间靠近查询。class Solution{public:boolisPalindrome(ListNode*head){vectorintvals;ListNode*curr=head;while(curr){vals.push_back(curr-val);// 拷贝值curr=curr-next;}intleft=0,right=vals.size()-1;while(leftright){if(vals[left++]!=vals[right--])returnfalse;}returntrue;}};方法二：js// 定义链表节点类（JS 无原生链表结构，需手动实现）classListNode{constructor(val){this.val=val;this.next=null;}}// 核心函数：判断链表是否为回文链表varisPalindrome=function(head){constvals=[];// 对应 C++ 的 vectorint vals，用于存储链表节点的值letcurr=head;// 遍历链表的指针，初始指向链表头节点// 遍历链表，将所有节点的值存入数组while(curr){// 等价于 C++ 的 while