您现在的位置是：首页 >学无止境 >代码随想录算法训练营第三天 | 链表理论基础 ，203.移除链表元素 ，707.设计链表，206.反转链表网站首页学无止境
代码随想录算法训练营第三天 | 链表理论基础 ，203.移除链表元素 ，707.设计链表，206.反转链表
简介代码随想录算法训练营第三天 | 链表理论基础 ，203.移除链表元素 ，707.设计链表，206.反转链表
链表理论基础
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
链表的入口节点称为链表的头结点也就是head。
如图所示：
- 链表的存储方式
数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
- 链表的定义
public class ListNode{
int val; // 节点上储存的元素
ListNode next; // 指向下一个节点的指针
public ListNode() {} // 无参构造
// 带参构造
public ListNode(int val) {
this.val=val;
}
public ListNode(int val, ListNode next) {
this.val=val;
this.next=next;
}
}
-
链表的操作
-
删除节点
-
添加节点
可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。
但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。 -
-
性能分析
数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。
链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。
203.移除链表元素
思路：
1. 找到满足条件节点的前一个节点，将该节点的下一个节点指向下下个节点(cur.next=cur.next.next)
2. 退出条件：目前节点的下个节点为空(cur.next!=null)
双指针法：
- 定义pre和cur两个指针，cur负责遍历链表，pre保持在cur前一个节点，循环结束条件为遍历所有节点(cur!=null)
- 找到满足条件的cur,使得该节点的前一个节点(pre)指向cur的下一个节点
注意：
涉及到头结点的更改最好定义一个虚拟头结点(dummy)，新的头结点为虚拟节点的下一个节点
-
Java代码
- 双指针法
class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy = new ListNode(0); dummy.next=head; ListNode cur = head; ListNode pre = dummy; while (cur!=null) { // 遍历所有的链表数据 if (cur.val==val) { pre.next=cur.next; } else { // 使得 pre 节点一直保持在 cur 的前一个节点 pre=cur; } cur=cur.next; } return dummy.next; } }时间复杂度:O(n)
空间复杂度:O(1)- 完整代码
package topic2ListNode; /*203. 移除链表元素 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5] 链接：https://leetcode.cn/problems/remove-linked-list-elements/*/ public class topic1_203 { public static void main(String[] args) { Solution solution = new topic1_203().new Solution(); int[] arr = {1,2,6,3,4,5,6}; int val = 6; ListNode head = new ListNode(arr); head.print(); ListNode newHead = solution.removeElements(head, val); newHead.print(); } class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy = new ListNode(0); dummy.next=head; ListNode cur = head; ListNode pre = dummy; // while (cur.next!=null) { // 思路有问题的 // if (cur.next.val==val) { // cur.next=cur.next.next; // } // if (cur==null) { // break; // } // cur=cur.next; // } while (cur!=null) { // 遍历所有的链表数据 if (cur.val==val) { pre.next=cur.next; } else { // 使得 pre 节点一直保持在 cur 的前一个节点 pre=cur; } cur=cur.next; } return dummy.next; } } }
707.设计链表
实现链表的功能
注意：index取值范围为 [0, size-1]
-
Java代码
- 代码实现
class MyLinkedList { int val; MyLinkedList next; int size=0; public MyLinkedList() { } public MyLinkedList(int val, MyLinkedList next) { this.val=val; this.next=next; } public int get(int index) { if (index<0 || index>=size) return -1; MyLinkedList cur = this; while (index-- >= 0) { cur=cur.next; } return cur.val; } public void addAtHead(int val) { addAtIndex(0, val); } public void addAtTail(int val) { addAtIndex(size, val); } public void addAtIndex(int index, int val) { if (index>=0 && index<=size) { MyLinkedList cur = this; while (index-->0) { cur=cur.next; } MyLinkedList newNode = new MyLinkedList(val, cur.next); cur.next=newNode; size++; } } public void deleteAtIndex(int index) { if (index>=0 && index<size) { // 不是 index<=size ，index取值为 [0, size-1] MyLinkedList pre = this; MyLinkedList cur = pre.next; while (index-- > 0) { pre=cur; cur=cur.next; } pre.next=cur.next; size--; } } }链表和节点最好分开操作，链表中有长度以及节点
class ListNode { int val; ListNode next; public ListNode() {} public ListNode(int val) { this.val=val; } public ListNode(int val, ListNode next) { this.val=val; this.next=next; } } class MyLinkedList { int size; ListNode head; public MyLinkedList() { size=0; head = new ListNode(); } public int get(int index) { if (index<0 || index>=size) return -1; ListNode cur = head; while (index-- >= 0) { cur=cur.next; } return cur.val; } public void addAtHead(int val) { addAtIndex(0, val); } public void addAtTail(int val) { addAtIndex(size, val); } public void addAtIndex(int index, int val) { if (index>=0 && index<=size) { ListNode cur = head; while (index-- > 0) { cur=cur.next; } ListNode newNode = new ListNode(val, cur.next); cur.next=newNode; size++; } } public void deleteAtIndex(int index) { if (index>=0 && index<size) { ListNode cur = head; while (index-- > 0) { cur=cur.next; } cur.next=cur.next.next; size--; } } }
206.反转链表
思路：
- 双指针指向前一个(pre)和后一个节点(cur)，保存下一个节点(temp)
- 将后一个节点指向前一个节点(cur.next=pre)，并移动双指针(pre=cur, cur=temp)
- 结束条件：后一个节点为空(cur!=null)，返回前一个节点(pre)
补充： - 使用虚拟头结点，并置为空(pre=null, cur=head)
- 增加剪枝操作，针对空链表和只有一个节点的链表
-
Java代码
- 双指针法
class Solution { public ListNode reverseList(ListNode head) { if (head==null || head.next==null) return head; ListNode pre = null; ListNode cur = head; ListNode temp; while (cur!=null) { temp=cur.next; cur.next=pre; pre=cur; cur=temp; } return pre; } }时间复杂度:O(n)
空间复杂度:O(1)- 完整代码
package topic2ListNode; /*206. 反转链表 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 示例 1： 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 链接：https://leetcode.cn/problems/reverse-linked-list/*/ public class topic3_206 { public static void main(String[] args) { Solution solution = new topic3_206().new Solution(); int[] arr = {1,2,3,4,5}; ListNode head = new ListNode(arr); head.print(); ListNode newHead = solution.reverseList(head); newHead.print(); } class Solution { public ListNode reverseList(ListNode head) { if (head==null || head.next==null) return head; ListNode pre = null; ListNode cur = head; ListNode temp; while (cur!=null) { temp=cur.next; cur.next=pre; pre=cur; cur=temp; } return pre; } } }
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述