山东网站,手机搭建wordpress 不root,怎样做网贷网站,销售网站开发背景意义leetCode-hot100-链表专题 链表简介单链表单链表的使用例题206.反转链表19.删除链表的倒数第N个结点24.两两交换链表中的节点25.K个一组翻转链表 双向链表双向链表的使用 循环链表61.旋转链表141.环形链表142.环形链表Ⅱ LinkedListLinkedList的使用 链表简介
参考博客#x… leetCode-hot100-链表专题 链表简介单链表单链表的使用例题206.反转链表19.删除链表的倒数第N个结点24.两两交换链表中的节点25.K个一组翻转链表 双向链表双向链表的使用 循环链表61.旋转链表141.环形链表142.环形链表Ⅱ LinkedListLinkedList的使用 链表简介
参考博客java数据结构之链表。 链表是一种常见的基础数据结构它由一系列节点组成每个节点包含数据域和一个或多个指针域用于指向其它节点。链表不像数组那样在内存中连续存储它的节点可以分散地存储在内存中通过指针连接起来。 链表的主要优点是它对插入和删除操作的效率很高尤其是当链表的长度变化很大时。在链表中进行插入和删除操作只需要改变相应节点的指针而不需要像数组那样进行大量元素的移动。而需要频繁查找元素的场景适合使用顺序表。
链表的主要类型包括
单向链表每个节点只包含一个指向下一个节点的指针。双向链表每个节点包含两个指针一个指向前一个节点一个指向下一个节点。循环链表链表中最后一个节点的指针指向第一个节点形成一个环。双向循环链表是双向链表和循环链表的结合每个节点有两个指针分别指向前一个节点和后一个节点并且最后一个节点的指针指向第一个节点。
需要理解的点 关于连续 链表在逻辑上是连续的但是物理上并不一定是连续的链表的结点一般都是从堆上申请由于每次都是按照一定的分配策略所以两次申请到的结点可能连续可能不连续。 关于“头” 链表中的头节点的data域中是空的一般编码设置头节点都是为了方便后续的操作不需要进行特殊处理而且可以简化链表的操作关于头节点看到的博文中有个很形象的比喻带不带头可以简单理解为有人驾驶的列车和无人驾驶的列车有人驾驶的列车不能在火车头前面加车厢第一节车厢永远是驾驶室而无人驾驶的列车则可以在最前面加车厢哪节车厢在最前面哪节就是头。即head只是用来标识。java数据结构之链表。这篇博文讲解了链表操作的底层逻辑文章的内容也是以此为参考很不戳建议大家都去读读 关于“循环” 判断是不是循环就看最后一个结点的next域存放的是null还是第一个结点的地址。
单链表
单链表的使用
方法备注addFirst(int data)将data插入链表头部addLast(int data)将data插入链表尾部addIndex(int index,int data)在下标为index位置插入data,第一个数据节点为0号下标contains(int key)查找关键字key是否在单链表当中remove(int key)删除第一次出现关键字为key的节点removeAllKey(int key)删除所有值为key的节点size()得到单链表的长度clear()清空链表display()从头结点开始遍历若该结点不等于null就打印输出该结点的元素
例题
206.反转链表
思路 本题是25.K个一组翻转链表25题中需要对分段的链表进行翻转而本题翻转整个链表直接翻转即可步骤如下
初始化两个指针pre和cur。pre开始时为null因为它需要指向当前节点cur之前的一个节点而反转开始前没有这样的节点。cur初始化为链表的头部head。进入一个循环只要cur不是null就执行循环体。这意味着只要当前节点不是链表的最后一个节点就继续反转。在循环内部首先使用一个临时节点next保存cur的下一个节点。这是必要的因为一旦cur.next被修改指向pre我们就失去了对原始下一个节点的引用。接下来将cur.next指向pre这是反转节点的关键步骤。然后将pre移动到它的新位置即当前的cur节点。最后将cur移动到下一个节点即之前保存在next中的节点。
当cur变为null时循环结束此时pre是新的头节点因为它指向原始链表的最后一个节点。 时间复杂度 这个算法的时间复杂度是O(n)其中n是链表的长度。这是因为算法会遍历整个链表一次每个节点都会被访问一次以进行反转。 代码实现
class Solution {public ListNode reverseList(ListNode head) {ListNode pre null;ListNode cur head;while(cur ! null){ListNode next cur.next;cur.next pre;pre cur;cur next;}return pre;}
}19.删除链表的倒数第N个结点
思路1 本题采用快慢指针来解决让快指针比慢指针先走n步当快指针到达链表尾部时慢指针所指向的下一个结点就是需要删除的倒数第n个结点在做链表相关的题目时一般需要在头节点的前面设置一个虚拟的结点方便边界的判断。详细的视频讲解点击视频讲解-删除链表的倒数第N个结点。
时间复杂度 时间复杂度为O(n)其中n是链表的长度。代码中有一个循环循环的次数是链表的长度n因此时间复杂度为O(n)。 代码实现
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy new ListNode(0);ListNode slow dummy;ListNode fast dummy;dummy.next head;//让快指针先向前走n步for(int i 0;i n;i){fastfast.next;}while(fast.next ! null){slow slow.next;fast fast.next;}//删除慢指针的下一个结点即需要删除的结点slow.next slow.next.next;return dummy.next;}
}思路2 删除链表的第n个节点比较简单所以我们可以先将链表翻转然后删除第n个节点后再次翻转即可其中翻转节点的操作在25.K个一组翻转链表以及206.反转链表中都有用到具体的步骤解释详细见206题的解析。 时间复杂度 时间复杂度为O(n)其中n为链表长度。 代码实现
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy new ListNode(0);//翻转链表删除第n个节点dummy.next reserve(head);ListNode cur dummy;//循环找到要删除节点的前一个节点for(int i 0; i n - 1; i){cur cur.next;}//删除第n个节点cur.next cur.next.next;//翻转链表得到删除倒数第n个节点的链表dummy.next reserve(dummy.next);return dummy.next;}//翻转链表private ListNode reserve(ListNode head){ListNode pre null;ListNode cur head;while(cur ! null){ListNode next cur.next;cur.next pre;pre cur;cur next;}return pre;}
}24.两两交换链表中的节点
思路 本题采用三指针来解决首先需要新建一个虚拟头节点方便操作然后分别新建三个指针指向虚拟头节点和头节点以及头节点的下一个节点通过操作三个指针使得节点互换位置然后将指针整体后移相同的操作。详细的讲解点击视频讲解-两两交换链表中的节点。
时间复杂度 时间复杂度为O(n)其中n是链表的长度。 代码实现
class Solution {public ListNode swapPairs(ListNode head) {ListNode dummy new ListNode(0);dummy.next head;//定义两个指针分别指向虚拟头节点dummy和其下一个节点ListNode pre dummy;ListNode cur dummy.next;while(cur ! null cur.next ! null){//定义第三个指针ListNode next cur.next;pre.next next;cur.next next.next;next.next cur;pre cur;cur cur.next;}return dummy.next;}
}25.K个一组翻转链表
思路 本题采用的思路是先将链表按K个节点一组分割然后单独对每一组进行翻转最后再拼接起来即可翻转函数逻辑比较简单就是采用三个指针每次让中间的指针刚开始指向头节点指向其前一个指针并整体后移重复操作。分割和拼接的操作其实也很简单如果看代码不太明白可以画个链表跟着操作走一遍就会明白每一步的含义代码里有注释希望对你有用详细的视频讲解点击视频讲解-K个一组翻转链表。 时间复杂度 时间复杂度为O(n)其中n是链表的长度。代码中有一个while循环每次循环都会处理k个节点反转、拼接所以循环的次数最多为n/k。在循环中反转操作的时间复杂度为O(k)拼接操作的时间复杂度为O(1)。因此总的时间复杂度可以近似为O(n)。 代码实现
class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode dummy new ListNode(0);dummy.next head;//定义首尾指针指向dummyListNode start dummy;ListNode end dummy;//按K个一组分割链表while(true){for(int i 0 ;i k end ! null;i) end end.next;if(end null) break;//分割后的链表的头节点ListNode startNext start.next;//分割后的剩余链表的头节点ListNode endNext end.next;//分割前K个节点end.next null;//对前K个节点的链表进行翻转start.next reverse(start.next);//将翻转后的链表的与剩余的节点拼接到一起startNext.next endNext;//更新头尾节点开始下一轮的翻转start end startNext;}return dummy.next;}//定义反转函数private ListNode reverse(ListNode head){ListNode cur head;ListNode pre null;while(cur ! null){ListNode next cur.next;//每次cur指针指向前一个节点达到翻转的目的然后将三个指针后移重复操作直到cur为空cur.next pre;pre cur;cur next;}return pre;}
}双向链表
双向链表相当于是单链表中的一种改进在单链表的基础上增加了一个前驱结点来存放前一个结点的位置这使得某些操作会更加简单。
双向链表的使用
双向链表的使用和单链表基本相同。
方法备注addFirst(int data)将data插入链表头部addLast(int data)将data插入链表尾部addIndex(int index,int data)在下标为index位置插入data,第一个数据节点为0号下标contains(int key)查找关键字key是否在单链表当中remove(int key)删除第一次出现关键字为key的节点removeAllKey(int key)删除所有值为key的节点size()得到单链表的长度clear()清空链表display()从头结点开始遍历若该结点不等于null就打印输出该结点的元素
循环链表
1.循环链表的表尾节点指针next指向头结点 2.循环链表从一个节点出发可以找到其他任意一个节点 3.循环链表的判空操作和普通单链表的判空方法基本相同不同之处在于循环链表的判空是判断头结点的指针是否指向头结点而普通单链表的判空是判断头结点的指针是否指向null 4.判断节点n是否为循环单链表的表尾节点和普通单链表的判断方法基本相同不同之处在于循环链表的判空是判断n节点的指针是否指向头结点而普通单链表的判空是判断n节点的指针是否指向null。
61.旋转链表
思路 1成环
首先检查链表是否为空如果为空则直接返回null。定义一个指针cur初始指向头节点head。遍历链表计算链表的长度n并将链表的最后一个节点指向头节点使链表形成一个环。
2找到需要分段的节点
再次遍历链表这次是为了找到新的头节点位置。由于旋转次数k可能大于链表长度n因此使用k % n来获取实际需要旋转的次数。循环n - k % n次找到旋转后链表的头节点的前一个节点即cur。
3改变头节点的位置断开环
将cur.next设置为新的头节点head。将cur.next设置为null断开环使链表恢复为线性结构。
4返回头节点 最后返回新的头节点head此时链表已经完成了旋转操作。视频讲解点击视频讲解-旋转链表。
时间复杂度 时间复杂度为O(n)其中n为链表的长度。 代码实现
class Solution {public ListNode rotateRight(ListNode head, int k) {if(head null) return null;//1.成环ListNode cur new ListNode();cur head;int n 1;while(cur.next ! null){cur cur.next;n;}cur.next head;//2.找到需要分段的节点for(int i 0;i n - k % n;i){cur cur.next;}//3.改变头节点的位置断开环head cur.next;cur.next null;return head;}
}141.环形链表
思路 本题主要是下面两个思想 快慢指针: 通过使用两个速度不同的指针在链表中遍历可以有效地检测环的存在。慢指针每次走一步快指针每次走两步。 相遇点: 如果链表中有环快指针会在环中追上慢指针最终导致两者相遇。如果没有环快指针会在到达链表末尾时终止。 为什么快指针不能每次移动三步或者更多呢快指针每次移动两步慢指针每次移动一步。这种配置保证了快指针的速度是慢指针的两倍。这样在最坏的情况下当链表中存在环时快指针和慢指针将在环中相遇在这种情况下相遇所需的步数最多是环长度的两倍。 如果快指针每次移动三步或更多步相遇的模式变得更复杂需要更多的步骤来分析和证明算法的正确性。同时更快的速度可能会跳过慢指针特别是在环比较小的情况下增加了算法的复杂性。视频讲解点击视频讲解-环形链表。 时间复杂度 时间复杂度为O(n)其中n为链表长度。 代码实现
public class Solution {public boolean hasCycle(ListNode head) {ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null){slow slow.next;fast fast.next.next;if(slow fast){return true;}}return false;}
}142.环形链表Ⅱ
思路 算法思想 1初始化
使用两个指针 fast 和 slow它们都从链表的头节点 head 开始。
2检测环的存在
在一个 while 循环中fast 指针每次移动两步slow 指针每次移动一步。如果链表中存在环fast 和 slow 指针最终会在环内相遇相同的节点。
3寻找环的起点
一旦 fast 和 slow 指针相遇将 slow 指针重新指向链表的头节点同时保持 fast 指针在相遇点。这时slow 和 fast 指针每次都移动一步。当它们再次相遇时相遇点就是环的起始节点。
证明 由上面的证明可知当slow和fast第一次相遇时此时让slow回到headfast从第一次相遇的点同步出发最终二者会在环的入点相遇fast回到headslow在第一次相遇点出发是同样的效果。
视频讲解点击视频讲解-环形链表Ⅱ。 时间复杂度 时间复杂度为O(mn)其中m为链表非环部分的长度n为环的长度无论链表的非环部分和环的长度如何算法的运行时间都与环的长度成线性关系所以时间复杂度可以简化为 O(n)。 代码实现
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null){slow slow.next;fast fast.next.next;//第一次相遇将slow置为头节点if(slow fast){slow head;while(slow ! fast){slow slow.next;fast fast.next;}return slow;}}return null;}
}LinkedList
LinkedList底层使用了双向链表并实现了List接口不支持随机访问但是在任意位置插入和删除元素的效率很高适合需要频繁插入和删除元素的场景。
LinkedList的使用
//创建一个空的LinkedList
ListInteger list new LinkedList()常用方法
方法备注add(e)在尾部插入eadd(int index, e)将e插入index位置addAll(C)将C中的元素全部插入尾部remove(int index)删除 index 位置元素remove(Object o)删除遇到的第一个 oget(int index)获取下标 index 位置元素set(int index, e)将下标 index 位置元素设置为 eclear()清空contains(Object o)判断 o 是否在线性表中indexOf(Object o)返回第一个 o 所在下标lastIndexOf(Object o)返回最后一个 o 的下标subList(int fromIndex, int toIndex)截取部分 list
三种遍历方法
//使用forEach遍历
for(int item : list){System.out.print(e );
}
//使用迭代器遍历-正向
ListIteratorInteger i1 list.listIterator();
while(i1.hasNext()){System.out.print(i1.next );
}
//使用迭代器遍历-反向
ListIteratorInteger i2 list.listIterator(list.size());
while (i2.hasPrevious()) {System.out.print(i2.previous() );
}
