赞
踩
链表是一种通过指针串联在一起的线性结构,每个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针)。
链表的入口节点被称为链表的头结点,也就是head。
1. 单链表
2. 双链表
单链表中的指针域只能指向节点的下一个节点。
双链表:每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点。
即可以向前查询也可以向后查询
3. 循环链表
循环链表就是链表首尾相连。
循环链表可以解决约瑟夫环问题
了解完链表的类型,再来说一说链表在内存中的存储方式。
数组是在内存中的连续分布的。但是链表在内存中不是连续分布的。
链表是通过指针域的指针链接再内存中的各个节点。
所以链表中的节点再内存中不是连续分布的,而是散乱分布在内存中的某地址上,分配机制取决于操作系统的内存管理。
这个链表起始节点为2,终止节点为7,各个节点分布在内存的不同地址空间上,通过指针串联在一起。
如果不定义构造函数使用默认构造函数的话,在初始化的时候就不能直接给变量赋值!
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; } }
1. 删除节点
删除D节点,如图所示
只要将C节点的next指针,指向E节点就好了。
那有同学说了,D节点不是依然存留在内存里么?只不过是没有在这个链表里而已。
是这样的,所以在C++里最好是再手动释放这个D节点,释放这块内存。
其他语言例如Java、Python,就有自己的内存回收机制,就不用自己手动释放了。
2. 添加节点
可以看出链表的增添和删除都是O(1)操作,也不会影响到其他节点。
但是要注意,要是删除第五个节点,需要从头节点查找到第四个节点通过next指针进行删除操作,查找的时间复杂度是O(n)。
再把链表的特性和数组的特性进行一个对比,如图所示:
数组在定义的时候,长度就是固定的,如果想改动数组的长度,就需要重新定义一个新的数组。
链表的长度可以是不固定的,并且可以动态增删, 适合数据量不固定,频繁增删,较少查询的场景。
题意:删除链表中等于给定值 val 的所有节点。
示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]
示例 2: 输入:head = [], val = 1 输出:[]
示例 3: 输入:head = [7,7,7,7], val = 7 输出:[]
这里以链表 1 4 2 4 来举例,移除元素4。
如果使用C,C++编程语言的话,不要忘了还要从内存中删除这两个移除的节点, 清理节点内存之后如图:
当然如果使用java ,python的话就不用手动管理内存了。
还要说明一下,就算使用C++来做leetcode,如果移除一个节点之后,没有手动在内存中删除这个节点,leetcode依然也是可以通过的,只不过,内存使用的空间大一些而已,但建议依然要养成手动清理内存的习惯。
这种情况下的移除操作,就是让节点next指针直接指向下下一个节点就可以了,
那么因为单链表的特殊性,只能指向下一个节点,刚刚删除的是链表的中第二个,和第四个节点,那么如果删除的是头结点又该怎么办呢?
这里就涉及如下链表操作的两种方式:
来看第一种操作:直接使用原来的链表来进行移除。
移除头结点和移除其他节点的操作是不一样的,因为链表的其他节点都是通过前一个节点来移除当前节点,而头结点没有前一个节点。
所以头结点如何移除呢,其实只要将头结点向后移动一位就可以,这样就从链表中移除了一个头结点。
依然别忘将原头结点从内存中删掉。
这样移除了一个头结点,是不是发现,在单链表中移除头结点 和 移除其他节点的操作方式是不一样,其实在写代码的时候也会发现,需要单独写一段逻辑来处理移除头结点的情况。
//移除链表元素(在原有链表的基础上进行操作) public ListNode removeElements(ListNode head, int val) { //如果头节点的值等于val,则需要删除头结点(在此处需要单独一段代码进行处理头节点)主要是为了保证头结点的值不是目标值,所以使用了while循环。 while(head!=null&&head.val==val) { head = head.next; } ListNode temp = head; while (temp!=null) { //如果找到目标值,将目标值进行删除,这里的删除逻辑只是将目标值的下一个节点,接到了temp节点上,实际上并没有对这个下一个节点进行判断,所以不能进行temp = temp.next操作 if(temp.next!=null&&temp.next.val==val) { temp.next = temp.next.next; } //此时temp的下一个节点不是目标值,所以可以放心的temp = temp.next else{ temp = temp.next; } } return head; }
时间复杂度O(n)
空间复杂度O(1)
那么可不可以 以一种统一的逻辑来移除 链表的节点呢。
其实可以设置一个虚拟头结点,这样原链表的所有节点就都可以按照统一的方式进行移除了。
来看看如何设置一个虚拟头。依然还是在这个链表中,移除元素1。
这里来给链表添加一个虚拟头结点为新的头结点,此时要移除这个旧头结点元素1。
这样是不是就可以使用和移除链表其他节点的方式统一了呢?
来看一下,如何移除元素1 呢,还是熟悉的方式,然后从内存中删除元素1。
最后呢在题目中,return 头结点的时候,别忘了 return dummyNode->next;
, 这才是新的头结点
//移除链表元素(虚拟头结点法) public ListNode removeElements(ListNode head, int val) { if (head == null) { return null; } //定义一个虚拟头结点 ListNode dummy = new ListNode(-1, head); //定义一个遍历节点 ListNode temp = dummy; while (temp != null) { if (temp.next != null && temp.next.val == val) { temp.next = temp.next.next; } else { temp = temp.next; } } return dummy.next; }
中间条件的判断还是用上边的方法。
时间复杂度O(n)
空间复杂度O(1)
题意:
在链表类中实现这些功能:
删除链表节点:
添加链表节点:
这道题目设计链表的五个接口:
可以说这五个接口,已经覆盖了链表的常见操作,是练习链表操作非常好的一道题目
链表操作的两种方式:
下面采用的设置一个虚拟头结点(这样更方便一些,大家看代码就会感受出来)。
单链表
/** * @description: 单链表 * @author: 李宋君 * @date: 2023/7/11 15:22 * @param: * @return: **/ class ListNode1 { int val; ListNode1 next; ListNode1() { } ListNode1(int val) { this.val = val; } } /** * @description: 使用单链表做的链表具体方法 * @author: 李宋君 * @date: 2023/7/11 14:26 * @param: * @return: **/ class MyLinkedList1 { //size存储链表元素的格式 int size; //虚拟头结点 ListNode1 head; //初始化链表 public MyLinkedList1() { size = 0; head = new ListNode1(0); } /** * @description: 获取第index个节点的数值, index是冲0开始的, 第0个节点是虚拟头结点 * @author: 李宋君 * @date: 2023/7/11 14:30 * @param: [index] * @return: int **/ public int get(int index) { if (index < 0 || index >= size) { //没有找到 return -1; } ListNode1 res = head; //从头结点开始遍历,遍历到目标为止 for (int i = 0; i <= index; i++) { res = res.next; } return res.val; } /** * @description: 在指定位置添加一个指定元素 * 如果index为0则,新插入的节点为链表的新头结点 * 如果index定于链表的长度,则说明新插入的节点为链表的尾节点 * 如果大于链表的长度,则返回空 * @author: 李宋君 * @date: 2023/7/11 14:37 * @param: [index, val] * @return: void **/ public void addAtIndex(int index, int val) { if (index > size) { return; } if (index < 0) { index = 0; } //先拿到要插入节点的前节点(虚拟头结点) ListNode1 pre = head; //找到目标节点的前驱节点 for (int i = 0; i < index; i++) { pre = pre.next; } ListNode1 addnode = new ListNode1(val); addnode.next = pre.next; pre.next = addnode; size++; } /** * @description: 删除指定节点index * @author: 李宋君 * @date: 2023/7/11 15:06 * @param: [index] * @return: void **/ public void deleteAtIndex(int index) { if (index < 0 || index >= size) { return; } if (index == 0) { head = head.next; } //前驱节点 ListNode1 pre = head; for (int i = 0; i < index; i++) { pre = pre.next; } pre.next = pre.next.next; size--; } /** * @description: 在链表的最前边加入一个节点, 等于在第0个元素前添加 * @author: 李宋君 * @date: 2023/7/11 14:36 * @param: [val] * @return: void **/ public void addAtHead(int val) { addAtIndex(0, val); } /** * @description: 在链表的最后加入节点 * @author: 李宋君 * @date: 2023/7/11 15:17 * @param: [val] * @return: void **/ public void addAtTail(int val) { addAtIndex(size, val); } }
双链表
/** * @description: 双链表结构 * @author: 李宋君 * @date: 2023/7/11 15:23 * @param: * @return: **/ class ListNode2 { int val; ListNode2 next, prev; ListNode2() { } ListNode2(int val) { this.val = val; } } class MyLinkList2 { //记录链表中元素的数量 int size; //记录链表的虚拟头结点和尾结点 ListNode2 head, tail; public MyLinkList2() { //初始化操作 this.size = 0; this.head = new ListNode2(0); this.tail = new ListNode2(0); //这一步非常关键,否则在加入头结点的操作中会出现null.next的错误!!! head.next = tail; tail.prev = head; } /** * @description: 获得指定节点 * @author: 李宋君 * @date: 2023/7/11 15:29 * @param: [index] * @return: int **/ public int get(int index) { //判断index是否有效 if (index < 0 || index >= size) { return -1; } ListNode2 cur = this.head; //判断是哪一边遍历时间更短 if (index >= size / 2) { //tail开始 cur = tail; for (int i = 0; i < size - index; i++) { cur = cur.prev; } } else { for (int i = 0; i <= index; i++) { cur = cur.next; } } return cur.val; } /** * @description: 在头结点处添加节点 * @author: 李宋君 * @date: 2023/7/11 15:30 * @param: [val] * @return: void **/ public void addAtHead(int val) { //等价于在第0个元素前添加 addAtIndex(0, val); } /** * @description: 在尾节点处添加节点 * @author: 李宋君 * @date: 2023/7/11 15:30 * @param: [val] * @return: void **/ public void addAtTail(int val) { //等价于在最后一个元素(null)前添加 addAtIndex(size, val); } /** * @description: 在指定位置添加节点 * @author: 李宋君 * @date: 2023/7/11 15:31 * @param: [index, val] * @return: void **/ public void addAtIndex(int index, int val) { //index大于链表长度 if (index > size) { return; } //index小于0 if (index < 0) { index = 0; } size++; //找到前驱 ListNode2 pre = this.head; for (int i = 0; i < index; i++) { pre = pre.next; } //新建结点 ListNode2 newNode = new ListNode2(val); newNode.next = pre.next; pre.next.prev = newNode; newNode.prev = pre; pre.next = newNode; } /** * @description: 在指定位置删除节点 * @author: 李宋君 * @date: 2023/7/11 15:31 * @param: [index] * @return: void **/ public void deleteAtIndex(int index) { //判断索引是否有效 if (index < 0 || index >= size) { return; } //删除操作 size--; ListNode2 pre = this.head; for (int i = 0; i < index; i++) { pre = pre.next; } pre.next.next.prev = pre; pre.next = pre.next.next; } }
给你单链表的头节点 head
,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2]
输出:[2,1]
示例 3:
输入:head = []
输出:[]
提示:
[0, 5000]
-5000 <= Node.val <= 5000
**进阶:**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
Related Topics
递归
链表
如果再定义一个新的链表,实现链表元素的反转,其实这是对内存空间的浪费。
其实只需要改变链表的next指针的指向,直接将链表反转 ,而不用重新定义一个新的链表,如图所示:
之前链表的头节点是元素1, 反转之后头结点就是元素5 ,这里并没有添加或者删除节点,仅仅是改变next指针的方向。
那么接下来看一看是如何反转的呢?
我们拿有示例中的链表来举例,如动画所示:(纠正:动画应该是先移动pre,在移动cur)
首先定义一个fast指针,指向头结点,再定义一个slow指针,初始化为null。
然后就要开始反转了,首先要把 fast->next 节点用tmp指针保存一下,也就是保存一下这个节点。
为什么要保存一下这个节点呢,因为接下来要改变 fast->next 的指向了,将fast->next 指向pre ,此时已经反转了第一个节点了。
接下来,就是循环走如下代码逻辑了,继续移动slow和fast指针。
最后,fast指针已经指向了null,循环结束,链表也反转完毕了。 此时我们return slow指针就可以了,slow指针就指向了新的头结点。
//反转链表(双指针法:前后双指针) public ListNode reverseList(ListNode head) { //当链表长度为0或者1时,直接返回链表 if (head == null || head.next == null) { return head; } //定义慢指针 ListNode slow = null; //定义快指针 ListNode fast = null; ListNode temp = null; while (true) { fast = head; //由于如果直接去修改fast.next = slow;会将head.next也变成null,因为是同一个对象,所以需要一个中间节点暂时保存head.next //然后再赋值 temp = head.next; fast.next = slow; slow = fast; head = temp; if (head == null) { break; } } return fast; }
时间复杂度O(n)
空间复杂度O(1)
使用前后指针说法可能有点难理解,所以换一种说法,就是将原来的链表变成两条链表
然后从原来的链表取头结点,接到新链表上。
关键:返回newHead 的next
//头插法 public ListNode reverseList(ListNode head) { //当链表长度为0或者1时,直接返回链表 if (head == null || head.next == null) { return head; } //新创建一个链表 ListNode newHead = new ListNode(5001); while(true) { //保存原来链表的下一个节点 ListNode temp = head.next; //先将原来链表的下一个节点插入新链表中 head.next = newHead.next; newHead.next = head; //最后将原来链表复原到下一个节点的位置 head = temp; if (head == null) { break; } } return newHead.next; }
第一次进入:newHead = 0,head = 1(1->2->3->4->5);
第二次进入:newHead = 0(0->1),head = 2(2->3->4->5);
第三次进入:newHead = 0(0->2->1),head = 3(3->4->5);
第四次进入:newHead = 0(0->3->2->1),head = 4(4->5);
第五次进入:newHead = 0(0->4->3->2->1),head = 5(5->null);
(也可以在开始将newHead.next()设置为1,能减少一次循环)
时间复杂度O(n)
空间复杂度O(1)
递归法相对抽象一些,但是其实和双指针法是一样的逻辑,同样是当cur为空的时候循环结束,不断将cur指向pre的过程。
关键是初始化的地方,可能有的同学会不理解, 可以看到双指针法中初始化 cur = head,pre = NULL,在递归法中可以从如下代码看出初始化的逻辑也是一样的,只不过写法变了。
具体可以看代码(已经详细注释),双指针法写出来之后,理解如下递归写法就不难了,代码逻辑都是一样的。
//递归法 public ListNode reverseList(ListNode head) { //递归入口 return reverse(head, null); } /** * @Description * @Param cur 当前节点(快指针) * @Param pre 当前节点的上一个节点(慢指针) * @Return {@link leetcode.editor.util.ListNode} * @Author 君君 * @Date 2024/6/24 22:35 */ private ListNode reverse(ListNode cur, ListNode pre) { //退出递归条件 if (cur == null) { return pre; } //递归核心代码 ListNode temp = cur.next; //将cur的next指针指向pre cur.next = pre; //将pre指针指向cur pre = cur; //cur向前移动一位 cur = temp; return reverse(cur, pre); }
时间复杂度O(n),要递归处理链表的每个节点
空间复杂度O(1)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。