java——LinkedList 我就是我 2024-03-30 14:05 62阅读 0赞 #### 文章目录 #### * LinkedList * * 1.基本介绍 * * 1.1常用方法 * 1.2ArrayList和LinkedList区别 * 2.具体应用 * * 2.1 LinkeList三种遍历 * * 2.1.1 代码 * 2.2 相交链表 * * 2.2.1题目描述 * 2.2.2 解题思路 * 代码 * 2.3 环形链表（是否有环） * * 2.3.1题目描述 * 2.3.2 解题思路 * 2.3.3 代码 * 2.4 环形链表（入口点） * * 2.4.1题目描述 * 2.4.2解题思路 * 代码 * 2.5 链表分割 * * 2.5.1 题目描述 * 2.5.2 解题思路 ## LinkedList ## ### 1.基本介绍 ### 1.LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。 2.结构如图所示： ![在这里插入图片描述][26e8bfae06c34ddb82b8f8486442f4ff.png] 3.在集合框架中，LinkedList也实现了List接口，具体如下： ![在这里插入图片描述][635502f776db487d833d51a4948293d2.png] 【说明】 1. LinkedList实现了List接口 2. LinkedList的底层使用了双向链表 3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问 4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1) 5. LinkedList比较适合任意位置插入的场景 #### 1.1常用方法 #### <table> <thead> <tr> <th>方法</th> <th>解释</th> </tr> </thead> <tbody> <tr> <td>boolean add(E e)</td> <td>尾插e</td> </tr> <tr> <td>void add(int index, E element)</td> <td>将 e 插入到 index 位置</td> </tr> <tr> <td>boolean addAll(Collection<? extends E> c)</td> <td>尾插 c 中的元素</td> </tr> <tr> <td>E remove(int index)</td> <td>删除 index 位置元素</td> </tr> <tr> <td>boolean remove(Object o)</td> <td>删除遇到的第一个 o</td> </tr> <tr> <td>E get(int index)</td> <td>获取下标 index 位置元素</td> </tr> <tr> <td>E set(int index, E element)</td> <td>将下标 index 位置元素设置为 element</td> </tr> <tr> <td>void clear()</td> <td>清空</td> </tr> <tr> <td>boolean contains(Object o)</td> <td>判断 o 是否在线性表中</td> </tr> <tr> <td>int indexOf(Object o)</td> <td>返回第一个 o 所在下标</td> </tr> <tr> <td>int lastIndexOf(Object o)</td> <td>返回最后一个o 所在下标</td> </tr> <tr> <td>List subList(int fromIndex, int toIndex)</td> <td>截取部分list</td> </tr> </tbody> </table> #### 1.2ArrayList和LinkedList区别 #### ![在这里插入图片描述][6f3d57a1aae34b1e86aefead24ee9d6e.png] ### 2.具体应用 ### #### 2.1 LinkeList三种遍历 #### ##### 2.1.1 代码 ##### //linkedlist的应用(遍历) LinkedList<String> linkedList = new LinkedList<String>(); linkedList.add("a"); linkedList.add("b"); linkedList.add("c"); linkedList.add("d"); linkedList.add("e"); //直接输出 System.out.println(linkedList); //for循环 for (String x : linkedList){ System.out.println(x); } //迭代器遍历(正向遍历 ListIterator<String> it = linkedList.listIterator(); while (it.hasNext()){ System.out.println(it.next()); } //反向遍历 while (it.hasPrevious()){ System.out.println(it.previous()); } #### 2.2 相交链表 #### ##### 2.2.1题目描述 ##### 给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。[相交链表][Link 1] 图示两个链表在节点 c1 开始相交： ![在这里插入图片描述][5bbd186b004140bb85083108727a8c68.png] ##### 2.2.2 解题思路 ##### 简单情况： 链表长度相同，定义两个指针同时遍历地址相同即为交点 ![image.png][] 其他情况： ![image.png][image.png 1] 链表长度不相同，同时遍历并不相交 解决办法：可以计算出两个链表长度差值，长的先走完差值，再同时遍历即可 ##### 代码 ##### /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null && headB == null) { return null; } //1、分别求两个链表的长度 int lenA = 0; int lenB = 0; ListNode pl = headA; ListNode ps = headB; while (pl != null) { lenA++; pl = pl.next; } while (ps != null) { lenB++; ps = ps.next; } //2. 要指回来 pl = headA; ps = headB; int len = lenA - lenB;//大小 //3、根据Length的值 修改指向 if(len < 0) { pl = headB; ps = headA; len = lenB-lenA; } //1. len一定是一个正数 2.pl指向的链表一定是最长的 ps 指向的链表一定是最短的 while (len != 0) { pl = pl.next; len--; } while (pl != ps) { pl = pl.next; ps = ps.next; } //pl == ps /* if(pl == null) { return null; } return pl;*/ return pl; } } #### 2.3 环形链表（是否有环） #### ##### 2.3.1题目描述 ##### 给你一个链表的头节点 head ，判断链表中是否有环。 如果链表中存在环 ，则返回 true 。 否则，返回 false 。[环形链表][Link 2] 示例 1： ![在这里插入图片描述][5f6925f473954b359831e7006824dd9d.png] 输入：head = \[3,2,0,-4\], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。 ##### 2.3.2 解题思路 ##### 转换为相遇问题，有环，一定会相遇。 定义快慢指针分别遍历链表，当快慢指针相遇时，即为环形链表。 此时定义快慢指针，所走步数为快指针两步，慢指针一步。 **注意**：此时快指针如果为3步…n步时可能会出现永远不会相遇的情况 如：极限可能，所走快的步数正好为一个圈，则永远不能相遇，犹豫一步不能构成一个圈，则看到会相遇。 ##### 2.3.3 代码 ##### /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { //定义快慢指针，指向头节点 ListNode fast = head; ListNode slow = head; //快指针走两步,即fast不为空和fast.next不为空时 //（fast.next.next为空无意义，fast走一步即为fast.next为空)遍历 while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { return true; } } return false; } } #### 2.4 环形链表（入口点） #### ##### 2.4.1题目描述 ##### 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。不允许修改 链表。[环形链表][Link 3] ##### 2.4.2解题思路 ##### 在寻找相交环的基础上，寻找入口点 存在技巧： ![image.png][image.png 2] 多圈则C非常小。 即 X == Y 则此时slow从起始点开始走，fast从相遇点开始走，相遇时即为入口点。 ##### 代码 ##### /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { //定义快慢指针 ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { //得到相遇点，即为fast此时指向节点 break; } } if(fast == null || fast.next == null) { return null; } //慢指针回到头节点，同时遍历，相遇时即为入口点 slow = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } } #### 2.5 链表分割 #### ##### 2.5.1 题目描述 ##### 现有一链表的头指针 ListNode\* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。[链表分割][Link 4] ##### 2.5.2 解题思路 ##### import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } 将链表分割为两个，定义四个节点 bs，be，as，ae分别表示两段链表的头和尾 本题可以采用，将小于x的节点头插到前面一段链表中,大于的放在后一段。但是需要考虑是否存在大于x的节点和小于x的节点。 }*/ public class Partition { public ListNode partition(ListNode pHead, int x) { // write code here ListNode bs = null; ListNode be = null; ListNode as = null; ListNode ae = null; ListNode cur = pHead; while (cur != null) { //小于插到前一段 if(cur.val < x) { //为空时，为bs、be赋值指向cur。 if(bs == null) { bs = cur; be = cur; }else { //不为空时插入be后面 be.next = cur; be = be.next; } //大于插入后一段 }else { 为空时，为as、ae赋值指向cur。 if(as == null) { as = cur; ae = cur; }else { //插入ae后面 ae.next = cur; ae = ae.next; } } cur = cur.next; } // 有可能不会同时存在小于x 和 大于等于x 的数据 //不存在小于的时候，不能直接 be.next = as; if(bs == null) { return as; } //第一段不为空，连接起来（第二段为空不影响） be.next = as; //第2个段为空不为空的问题，加if判断为不为空，不能1直接将ae.next置空以免空指针异常 if(as != null) { ae.next = null; } return bs; } } [26e8bfae06c34ddb82b8f8486442f4ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/1aba4d608350431ebcd5a8023cb12fd5.png [635502f776db487d833d51a4948293d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/57f9760fc7e74ea18f3fd8639a7b83a1.png [6f3d57a1aae34b1e86aefead24ee9d6e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/873e514f65424c9592ae3309f0ca4f07.png [Link 1]: https://leetcode.cn/problems/intersection-of-two-linked-lists/ [5bbd186b004140bb85083108727a8c68.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3ce179b5e6a7465c844c8d5a70ce6335.png [image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/47ba1ac8539e4726b56a8fa258a3fd70.png [image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9262091d50aa4670b4dec618bc5bf395.png [Link 2]: https://leetcode.cn/problems/linked-list-cycle/ [5f6925f473954b359831e7006824dd9d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/92fbdb9d93654d9fb09514a9baaefca8.png [Link 3]: https://leetcode.cn/problems/linked-list-cycle-ii/ [image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/501e6d574a5643e68095215257997ac6.png [Link 4]: https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
还没有评论，来说两句吧...