北京网站建设 网络推广,做网站需要填什么,品牌互动营销案例,合肥网红打卡地目录
2. 链表相关题目
2.1 合并两个有序链表#xff08;简单#xff09;#xff1a;递归
2.2 删除排序链表中的重复元素#xff08;简单#xff09;#xff1a;一次遍历
2.3 两链表相加#xff08;中等#xff09;#xff1a;递归
2.4 删除链表倒数第N个节点简单递归
2.2 删除排序链表中的重复元素简单一次遍历
2.3 两链表相加中等递归
2.4 删除链表倒数第N个节点中等倒数第N个元素是遍历的第L-N1个元素
2.5 两两交换链表中的节点中等递归
2.6 旋转链表中等链表成环后断开
2.7 判断是否存在环形链表简单Set集合 重复判断
2.8 环形链表若存在返回其入环的第一个节点中等Set集合 重复判断
2.9 LRU缓存(中等也可以说困难)哈希表 双向链表
2.10 反转链表简单迭代
2.11 分隔链表中等
2.12 反转给定节点处的链表中等穿针引线
2.13 链表的总结 2. 链表相关题目
2.1 合并两个有序链表简单递归
题目将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
思想将两个链表头部值中较小的一个节点和剩下元素的merge操作合并 总结将链表头部单独拿出来先比较比较完后确立了合并链表的头部剩下的元素按照这种思路继续比较 代码
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {//判断 list1 或者 list2 是否为空为空则直接返回if(list1 null){return list2;}else if(list2 null){return list1;}//如果list1头部更小则list1头部作为合并后链表的头部然后继续合并其它链表else if(list1.val list2.val){list1.next mergeTwoLists(list1.next, list2);return list1;}//如果list2头部更小则list2头部作为合并后链表的头部然后继续合并其它链表else{list2.next mergeTwoLists(list1,list2.next);return list2;}}
} 2.2 删除排序链表中的重复元素简单一次遍历
题目给定一个已排序的链表的头 head 删除所有重复的元素使每个元素只出现一次 。返回 已排序的链表
思想给定的链表是已经排好序的重复的元素在链表中出现的位置是连续的因此我们比较curr和curr.next若相等则删除curr.next 总结curr.next不为空时判断curr和curr.next是否相等 相等则删除curr.next 不相等则继续判断下一个节点 代码
class Solution {public ListNode deleteDuplicates(ListNode head) {if (head null) {return head;}
ListNode cur head;while (cur.next ! null) {if (cur.val cur.next.val) {cur.next cur.next.next;} else {cur cur.next;}}
return head;}
} 2.3 两链表相加中等递归
题目给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。
请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头。
思想链表都是逆序存储数字的因此链表中同一位置的数可以直接相加且 sum l1.val l2.val carry 存入结果链表的是 % 10之后的值 下一次的carry是 / 10之后的值 总结使用递归法将每一次的sum求出然后十进制转换后存入结果链表 代码
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {return add(l1, l2, 0);}
public ListNode add(ListNode l1, ListNode l2, int carry){//如果l1、l2为空且此时carry进位为0;则返回nullif(l1 null l2 null carry 0){return null;}//sum l1.val l2.val carryif(l1 ! null){carry l1.val;l1 l1.next;}if(l2 ! null){carry l2.val;l2 l2.next;}//将相加后的数 % 10然后存入结果链表ListNode result new ListNode(carry % 10);
//递归并将新的carry值传入为下一次sum做准备result.next add(l1, l2, carry / 10);
return result;}
} 2.4 删除链表倒数第N个节点中等倒数第N个元素是遍历的第L-N1个元素
题目给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点
思想首先得到链表的长度L从头节点开始遍历到第L - N 1个节点时该节点就是需要删除的节点 总结创建一个哑节点用来指向链表的第一个节点从头节点开始遍历1 -- L - N - 1该节点的下一个节点即是待删除元素 代码
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//创建一个哑节点指向第一个元素ListNode dummy new ListNode(0,head);
//获取链表长度int length getLength(head);
//将哑节点作为当前元素ListNode curr dummy;
//获得倒数第N个节点的前一个结点从i 1 遍历到l - n 1之前第l - n 1个节点就是该节点for(int i 1; i length - n 1; i){//每遍历一次都将下一个节点值赋给该节点curr curr.next;}
//遍历完后下一个节点值就是待删除节点值curr.next curr.next.next;
ListNode result dummy.next;return result;
}
public int getLength(ListNode head){int length 0;while(head ! null){length;head head.next;}return length;}
} 2.5 两两交换链表中的节点中等递归
题目给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题
思想首先交换头节点和第二个节点的位置然后递归的实现第三个节点、第四个节点、、、的交换结束条件是链表中没有节点或者只剩下一个节点 原始链表的头节点head新链表的第二个节点 原始链表的第二个节点新链表的头节点newhead 原始链表其他节点的头节点newhead 原始链表其他节点交换后是放在原始链表头部节点此时是新链表的第二个节点的后面的 总结重点是交换时的顺序 先找到新链表的头节点 然后根据新链表的头节点找到该节点在原始链表中的下一个节点来递归 最后将原始节点的头节点作为新链表的第二个节点 代码
class Solution {public ListNode swapPairs(ListNode head) {if(head null || head.next null){return head;}
//原始链表头部的下一个节点就是新链表的头节点ListNode newHead head.next;//这两行的顺序不能变化因为此时是对原始链表的第三个节点进行的交换若先将head赋值给newHead.next就没有了意义//新链表头节点在原始链表中的下一个节点第三个节点就是head的下一个节点head.next swapPairs(newHead.next);
//head是新链表节点的下一个节点newHead.next head;
return newHead;}
} 2.6 旋转链表中等链表成环后断开
题目给你一个链表的头节点 head 旋转链表将链表每个节点向右移动 k 个位置。
思想若链表长度为n则 若向右移动的k n时实际上移动k mod n次 新链表的最后一个节点是原链表的第 (n-1)-(k mod n)个节点 将链表连接成环将链表的尾节点连接上头节点然后找到新链表的最后一个节点将其断开即可 总结创建一个哑节点用来指向链表的第一个节点从头节点开始遍历1 -- L - N - 1该节点的下一个节点即是待删除元素 代码
class Solution {public ListNode rotateRight(ListNode head, int k) {//1.若不移动或者根节点为空或者只有一个根节点if(k 0 || head null || head.next null){return head;}
//2.计算出链表长度从1开始计数此时即head一定有值int n 1;ListNode curr head;while(curr.next ! null){n;curr curr.next;}
//3.新链表的最后一个节点是原链表的第n - k mod n个节点从1开始计数int add n - k % n;//如果最后一个节点n - k mod n等于原链表的第n个节点说明k为n的倍数不需要旋转if(add n){return head;}
//4.将链表成环然后找到新链表的最后一个节点原链表的第n -k mod n个节点将其断开curr.next head; //链表成环
//找到旋转后新链表的最后一个节点while(add 0){curr curr.next;add--;}//闭环中新链表的最后一个节点的下一个节点就是新链表的头节点ListNode result curr.next;
//将环断开curr.next null;
return result;
}
}
2.7 判断是否存在环形链表简单Set集合 重复判断
题目给你一个链表的头节点 head 判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况
思想遍历所有节点每遍历到一个节点就存入哈希表中并判断该节点是否被访问过如果存在环形链表则遍历的过程中会出现环形链表的节点会被访问两次第一个被访问两次的节点就是环形链表的头节点位置若访问过则说明是环形链表 总结遍历链表存入set集合利用set集合的自身特性来判断 代码
public class Solution {public boolean hasCycle(ListNode head) {//用一个HashSet集合存储每次遍历过程中链表中的节点SetListNode set new HashSet();
while(head ! null){//set是无需不可重复的若set.add()返回false说明已添加过该节点if(!set.add(head)){return true;}//节点后移head head.next;}
//遍历结束仍不存在相同节点说明没有环形链表存在return false;}
} 2.8 环形链表若存在返回其入环的第一个节点中等Set集合 重复判断
题目给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况
思想遍历所有节点每遍历到一个节点就存入哈希表中并判断该节点是否被访问过如果存在环形链表则遍历的过程中会出现环形链表的节点会被访问两次第一个被访问两次的节点就是环形链表的头节点位置若访问过则说明是环形链表且第一个访问到的重复访问节点就是入环的第一个节点 总结遍历链表存入set集合利用set集合的自身特性来判断如果存在则直接返回该节点不存在则加入set中 代码
public class Solution {public ListNode detectCycle(ListNode head) {//创建存储集合setSetListNode set new HashSet();ListNode curr head;
//遍历链表中的所有值while(curr ! null){//判断是否存在重复节点存在一定是第一个节点直接返回不存在则继续遍历下一个if(set.contains(curr)){return curr;}else{set.add(curr);}curr curr.next;}//不存在返回nullreturn null;}
} 2.9 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) 的平均时间复杂度运行。
思想
LRU 缓存机制可以通过哈希表辅以双向链表实现我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。 双向链表按照被使用的顺序存储了这些键值对靠近头部的键值对是最近使用的而靠近尾部的键值对是最久未使用的。 哈希表即为普通的哈希映射HashMap通过缓存数据的键映射到其在双向链表中的位置。
这样以来我们首先使用哈希表进行定位找出缓存项在双向链表中的位置随后将其移动到双向链表的头部即可在 O(1)O(1)O(1) 的时间内完成 get 或者 put 操作。具体的方法如下 对于get 操作首先判断 key 是否存在 如果 key不存在则返回 −1 如果key 存在则key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置并将其移动到双向链表的头部最后返回该节点的值。 对于put操作首先判断 key是否存在 如果 key 不存在使用key和 value 创建一个新的节点在双向链表的头部添加该节点并将 key和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量如果超出容量则删除双向链表的尾部节点并删除哈希表中对应的项 如果key 存在则与get操作类似先通过哈希表定位再将对应的节点的值更新为 value并将该节点移到双向链表的头部。 总结遍历链表存入set集合利用set集合的自身特性来判断如果存在则直接返回该节点不存在则加入set中 代码
class LRUCache {class MyLinkedNode{int key;int value;MyLinkedNode prev;MyLinkedNode next;public MyLinkedNode(){}public MyLinkedNode(int key,int value){this.key key;this.value value;}}//需要使用哈希表和双向链表需要自己实现来实现//哈希表用来快速定位缓存中的元素所在位置从而方便的get与put;哈希表中存储索引值和双向链表值链表有key及valueprivate MapInteger,MyLinkedNode cache new HashMap();
//记录链表长度private int size;//记录LRU容量private int capacity;//定义两个哑节点用来指向链表的头尾节点private MyLinkedNode head;private MyLinkedNode tail;
//创建时定义LRU的size与capacity并创建头尾伪节点public LRUCache(int capacity) {this.size size;this.capacity capacity;//构建头尾指针head new MyLinkedNode();tail new MyLinkedNode();head.next tail;tail.prev head;}//get时先判断Map是否存在该节点若不存在返回-1若存在则将其展示并把它移动到双向链表的头部public int get(int key) {MyLinkedNode node cache.get(key);if(node null){return -1;}//将节点移动到双向链表的头部moveToHead(node);return node.value;}//put时先判断Map中是否存在该节点若存在则直接改变value并将其移动到头部//若不存在则将其添加到哈希表和链表头部并判断当链表长度sizeLRU容量则将链表尾部节点删除public void put(int key, int value) {MyLinkedNode node cache.get(key);if(node ! null){//存在该节点则改变其value值node.value value;moveToHead(node);}else{//将节点添加到链表和哈希表中然后移动到链表头部MyLinkedNode newNode new MyLinkedNode(key,value);cache.put(key,newNode);addToHead(newNode);size;
//判断是否超出容量超出则在链表和哈希表中删除尾部节点if(size capacity){MyLinkedNode tail removeTail();cache.remove(tail.key);size--;}}}
public void moveToHead(MyLinkedNode node){removeNode(node);addToHead(node);}
//删除节点public void removeNode(MyLinkedNode node){node.prev.next node.next;node.next.prev node.prev;}
//将节点添加到头部public void addToHead(MyLinkedNode node){node.prev head;node.next head.next;head.next.prev node;head.next node;}
//删除尾部节点:拿到尾部节点然后删除并返回删除后的节点public MyLinkedNode removeTail(){MyLinkedNode result tail.prev;removeNode(result);return result;}
} 2.10 反转链表简单迭代
题目给你单链表的头节点 head 请你反转链表并返回反转后的链表。
思想遍历链表让遍历的节点的next指向前一个节点注意头节点没有引用前一个节点因此要先存储一个前节点为null并且要创建一个新节点最终返回新的链表头部 总结在进行反转时需要变化的量有节点值为了迭代变为下一个节点值、节点的下一个值指向节点的上一个值、节点的上一个值为了迭代每次变为上一次迭代的当前节点值 代码
class Solution {public ListNode reverseList(ListNode head) {//创建一个空节点用来指向nullListNode prev null;//创建一个临时节点ListNode curr head;
//如果当前节点不为空反转链表时//当前节点的下一个节点先存下来然后将让当前节点的next指向前一个结点//每轮循环中前一个节点都是上一次循环的当前节点while(curr ! null){ListNode next curr.next;curr.next prev;prev curr;curr next;}return prev;}
} 2.11 分隔链表中等
题目给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 保留 两个分区中每个节点的初始相对位置
思想维护两个链表samll和large按照顺序分别存储小于x的节点值和大于等于x的节点值最后将前一个链表的尾节点指向钱一个链表的头节点即可 总结为防止头节点的边界条件需要对头节点进行特殊判断为了防止这个特殊判断设置一个哑节点指向头节点 代码
class Solution {public ListNode partition(ListNode head, int x) {//创建两个链表分别用来存储小于x和大于等于x的节点ListNode small new ListNode(0);ListNode large new ListNode(0);
//创建两个哑节点此时哑节点并不指向新链表的头节点而是等于头节点后面讲头节点改为新添加的节点ListNode smallHead small;ListNode largeHead large;
//遍历当前链表值根据与x的比较存入两个新链表while(head ! null){//将小于x的节点存入small链表并更改头部if(head.val x){small.next head;small small.next;}//将大于等于x的节点存入large链表并更改头部else{large.next head;large large.next;}head head.next;}//将samll的尾节点指向large的头节点small.next largeHead.next;//将large的尾节点指向nullarge.next null;return smallHead.next;}
} 2.12 反转给定节点处的链表中等穿针引线
题目给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 保留 两个分区中每个节点的初始相对位置
思想先将需要反转的位置进行反转得到反转后链表然后将left的前一个节点prev指向反转后的链表的头部将反转后链表的尾部指向right的next节点即可 总结只要是头节点可能发生变化的情况都设置一个哑节点用来处理这种特殊情况 代码
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {//创建一个哑节点指向链表头部ListNode dummy new ListNode();dummy.next head;
//一开始记left的前一个节点为哑节点然后从哑节点出发走left - 1步找到left节点的前一个节点prevListNode prev dummy;for(int i 0; i left - 1; i){prev prev.next;}
//从prev出发走right - left 1 步找到right节点ListNode rightNode prev;for(int i 0; i right - left 1; i){rightNode rightNode.next;}
//先将prev的下一个节点left和rightNode的下一个节点next保存起来然后将链表截断ListNode leftNode prev.next;ListNode next rightNode.next;prev.next null;rightNode.next null;
//将截断后的元素进行反转reverseListNode(leftNode);
//让prev节点指向新链表的头节点rightNode新链表的尾节点leftNode指向保存下的next节点prev.next rightNode;leftNode.next next;return dummy.next;
}
public void reverseListNode(ListNode head){ListNode prev null;ListNode curr head;while(curr ! null){ListNode next curr.next;curr.next prev;prev curr;curr next;}}
}
2.13 链表的总结
链表主要注意几点 对于头节点可能发生变化的情况可以设置一个哑节点用来指向头节点从而减少对头节点特殊情况的判断同理特殊情况也可以构造尾节点的哑节点 链表中的指针很神奇能够控制链表的指向若指向null或者指向头部就能轻松改变一个链表的状态使之断开或者成环谨慎改变指针的指向能够解决很多问题 在树结构中很多时候可以使用递归链表中也一样因为都是一样的结构构造好递归函数就能省去很多时间
