建设部证书查询网站,网站建设公式,网站做一些流量互换,小清新个人网站#x1f49d;#x1f49d;#x1f49d;欢迎来到我的博客#xff0c;很高兴能够在这里和您见面#xff01;希望您在这里可以感受到一份轻松愉快的氛围#xff0c;不仅可以获得有趣的内容和知识#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学… 欢迎来到我的博客很高兴能够在这里和您见面希望您在这里可以感受到一份轻松愉快的氛围不仅可以获得有趣的内容和知识也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老导航 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂 非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。 ✨✨ 欢迎订阅本专栏 ✨✨ 博客目录 一.认识链表1.链表定义与分类2.哨兵节点3.查询性能4.插入和删除性能 二.单向链表1.定义2.头部添加3.while 遍历4.for 遍历5.迭代器遍历6.递归遍历7.尾部添加8.尾部添加多个9.根据索引获取10.插入11.删除 三.单向链表带哨兵1.带哨兵单向链表2.获取索引节点3.插入删除节点 四.双向链表带哨兵五.环形链表带哨兵六.解题模版1.反转链表再正向遍历2.递归遍历 七.链表题目1.两数相加2.两数相加 II3.合并两个有序链表4.删除排序链表中的重复元素5.环形链表6.相交链表7.移除链表元素8.反转链表9.回文链表10.链表的中间结点 一.认识链表
1.链表定义与分类
在计算机科学中链表是数据元素的线性集合其每个元素都指向下一个元素元素存储上并不连续
可以分类为.
单向链表每个元素只知道其下一个元素是谁 双向链表每个元素知道其上一个元素和下一个元素 循环链表通常的链表尾节点 tail 指向的都是 null而循环链表的 tail 指向的是头节点 head 2.哨兵节点
链表内还有一种特殊的节点称为哨兵Sentinel节点也叫做哑元 Dummy节点它不存储数据通常用作头尾用来简化边界判断如下图所示 3.查询性能
随机访问性能
根据 index 查找时间复杂度 O(n)
4.插入和删除性能
插入或删除性能
起始位置O(1)结束位置如果已知 tail 尾节点是 O(1)不知道 tail 尾节点是 O(n)中间位置根据 index 查找时间 O(1)
二.单向链表
1.定义
根据单向链表的定义首先定义一个存储 value 和 next 指针的类 Node和一个描述头部节点的引用
public class SinglyLinkedList {private Node head; // 头部节点private static class Node { // 节点类int value;Node next;public Node(int value, Node next) {this.value value;this.next next;}}
}Node 定义为内部类是为了对外隐藏实现细节没必要让类的使用者关心 Node 结构定义为 static 内部类是因为 Node 不需要与 SinglyLinkedList 实例相关多个 SinglyLinkedList 实例能共用 Node 类定义
2.头部添加
public class SinglyLinkedList {// ...public void addFirst(int value) {this.head new Node(value, this.head);}
}如果 this.head null新增节点指向 null并作为新的 this.head如果 this.head ! null新增节点指向原来的 this.head并作为新的 this.head 注意赋值操作执行顺序是从右到左
3.while 遍历
public class SinglyLinkedList {// ...public void loop() {Node curr this.head;while (curr ! null) {// 做一些事curr curr.next;}}
}4.for 遍历
public class SinglyLinkedList {// ...public void loop() {for (Node curr this.head; curr ! null; curr curr.next) {// 做一些事}}
}以上两种遍历都可以把要做的事以 Consumer 函数的方式传递进来 Consumer 的规则是一个参数无返回值因此像 System.out::println 方法等都是 Consumer调用 Consumer 时将当前节点 curr.value 作为参数传递给它
//使用Consumer传参
public void loop4(ConsumerInteger consumer) {Node p head;while (p ! null) {consumer.accept(p.value);p p.next;}
}//测试
Test
DisplayName(测试 consumer while遍历 loop4)
public void test5() {SinglyLinkedList list new SinglyLinkedList();list.addFirst(1);list.addFirst(2);list.addFirst(3);list.addFirst(4);ConsumerInteger consumer integer - System.out.println(integer);list.loop4(consumer);
}5.迭代器遍历
public class SinglyLinkedList implements IterableInteger {// ...private class NodeIterator implements IteratorInteger {Node curr head;public boolean hasNext() {return curr ! null;}public Integer next() {int value curr.value;curr curr.next;return value;}}public IteratorInteger iterator() {return new NodeIterator();}
}hasNext 用来判断是否还有必要调用 nextnext 做两件事 返回当前节点的 value指向下一个节点 NodeIterator 要定义为非 static 内部类是因为它与 SinglyLinkedList 实例相关是对某个 SinglyLinkedList 实例的迭代
6.递归遍历
public class SinglyLinkedList implements IterableInteger {// ...public void loop() {recursion(this.head);}private void recursion(Node curr) {if (curr null) {return;}//前面做些事recursion(curr.next);//后面做些事}
}7.尾部添加
public class SinglyLinkedList {// ...private Node findLast() {if (this.head null) {return null;}Node curr;for (curr this.head; curr.next ! null; ) {curr curr.next;}return curr;}public void addLast(int value) {Node last findLast();if (last null) {addFirst(value);return;}last.next new Node(value, null);}
}注意找最后一个节点终止条件是 curr.next null分成两个方法是为了代码清晰而且 findLast() 之后还能复用
8.尾部添加多个
public class SinglyLinkedList {// ...public void addLast(int first, int... rest) {Node sublist new Node(first, null);Node curr sublist;for (int value : rest) {curr.next new Node(value, null);curr curr.next;}Node last findLast();if (last null) {this.head sublist;return;}last.next sublist;}
}先串成一串 sublist再作为一个整体添加
9.根据索引获取
public class SinglyLinkedList {// ...private Node findNode(int index) {int i 0;for (Node curr this.head; curr ! null; curr curr.next, i) {if (index i) {return curr;}}return null;}private IllegalArgumentException illegalIndex(int index) {return new IllegalArgumentException(String.format(index [%d] 不合法%n, index));}public int get(int index) {Node node findNode(index);if (node ! null) {return node.value;}throw illegalIndex(index);}
}同样分方法可以实现复用
10.插入
public class SinglyLinkedList {// ...public void insert(int index, int value) {if (index 0) {addFirst(value);return;}Node prev findNode(index - 1); // 找到上一个节点if (prev null) { // 找不到throw illegalIndex(index);}prev.next new Node(value, prev.next);}
}插入包括下面的删除都必须找到上一个节点
11.删除
public class SinglyLinkedList {// ...public void remove(int index) {if (index 0) {if (this.head ! null) {this.head this.head.next;return;} else {throw illegalIndex(index);}}Node prev findNode(index - 1);Node curr;if (prev ! null (curr prev.next) ! null) {prev.next curr.next;} else {throw illegalIndex(index);}}
}第一个 if 块对应着 removeFirst 情况最后一个 if 块对应着至少得两个节点的情况 不仅仅判断上一个节点非空还要保证当前节点非空
三.单向链表带哨兵
1.带哨兵单向链表
观察之前单向链表的实现发现每个方法内几乎都有判断是不是 head 这样的代码能不能简化呢
用一个不参与数据存储的特殊 Node 作为哨兵它一般被称为哨兵或哑元拥有哨兵节点的链表称为带头链表
public class SinglyLinkedListSentinel {// ...private Node head new Node(Integer.MIN_VALUE, null);
}具体存什么值无所谓因为不会用到它的值
2.获取索引节点
加入哨兵节点后代码会变得比较简单先看几个工具方法
public class SinglyLinkedListSentinel {// ...// 根据索引获取节点private Node findNode(int index) {int i -1;for (Node curr this.head; curr ! null; curr curr.next, i) {if (i index) {return curr;}}return null;}// 获取最后一个节点private Node findLast() {Node curr;for (curr this.head; curr.next ! null; ) {curr curr.next;}return curr;}
}findNode 与之前类似只是 i 初始值设置为 -1 对应哨兵实际传入的 index 也是 [-1, \infty)findLast 绝不会返回 null 了就算没有其它节点也会返回哨兵作为最后一个节点
3.插入删除节点
这样代码简化为
public class SinglyLinkedListSentinel {// ...public void addLast(int value) {Node last findLast();/*改动前if (last null) {this.head new Node(value, null);return;}*/last.next new Node(value, null);}public void insert(int index, int value) {/*改动前if (index 0) {this.head new Node(value, this.head);return;}*/// index 传入 0 时返回的是哨兵Node prev findNode(index - 1);if (prev ! null) {prev.next new Node(value, prev.next);} else {throw illegalIndex(index);}}public void remove(int index) {/*改动前if (index 0) {if (this.head ! null) {this.head this.head.next;return;} else {throw illegalIndex(index);}}*/// index 传入 0 时返回的是哨兵Node prev findNode(index - 1);Node curr;if (prev ! null (curr prev.next) ! null) {prev.next curr.next;} else {throw illegalIndex(index);}}public void addFirst(int value) {/*改动前this.head new Node(value, this.head);*/this.head.next new Node(value, this.head.next);// 也可以视为 insert 的特例, 即 insert(0, value);}
}对于删除前面说了【最后一个 if 块对应着至少得两个节点的情况】现在有了哨兵就凑足了两个节点
四.双向链表带哨兵
public class DoublyLinkedListSentinel implements IterableInteger {private final Node head;private final Node tail;public DoublyLinkedListSentinel() {head new Node(null, 666, null);tail new Node(null, 888, null);head.next tail;tail.prev head;}private Node findNode(int index) {int i -1;for (Node p head; p ! tail; p p.next, i) {if (i index) {return p;}}return null;}public void addFirst(int value) {insert(0, value);}public void removeFirst() {remove(0);}public void addLast(int value) {Node prev tail.prev;Node added new Node(prev, value, tail);prev.next added;tail.prev added;}public void removeLast() {Node removed tail.prev;if (removed head) {throw illegalIndex(0);}Node prev removed.prev;prev.next tail;tail.prev prev;}public void insert(int index, int value) {Node prev findNode(index - 1);if (prev null) {throw illegalIndex(index);}Node next prev.next;Node inserted new Node(prev, value, next);prev.next inserted;next.prev inserted;}public void remove(int index) {Node prev findNode(index - 1);if (prev null) {throw illegalIndex(index);}Node removed prev.next;if (removed tail) {throw illegalIndex(index);}Node next removed.next;prev.next next;next.prev prev;}private IllegalArgumentException illegalIndex(int index) {return new IllegalArgumentException(String.format(index [%d] 不合法%n, index));}Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node p head.next;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic Integer next() {int value p.value;p p.next;return value;}};}static class Node {Node prev;int value;Node next;public Node(Node prev, int value, Node next) {this.prev prev;this.value value;this.next next;}}
}五.环形链表带哨兵
双向环形链表带哨兵这时哨兵既作为头也作为尾 参考实现
public class DoublyLinkedListSentinel implements IterableInteger {Overridepublic IteratorInteger iterator() {return new Iterator() {Node p sentinel.next;Overridepublic boolean hasNext() {return p ! sentinel;}Overridepublic Integer next() {int value p.value;p p.next;return value;}};}static class Node {Node prev;int value;Node next;public Node(Node prev, int value, Node next) {this.prev prev;this.value value;this.next next;}}private final Node sentinel new Node(null, -1, null); // 哨兵public DoublyLinkedListSentinel() {sentinel.next sentinel;sentinel.prev sentinel;}/*** 添加到第一个* param value 待添加值*/public void addFirst(int value) {Node next sentinel.next;Node prev sentinel;Node added new Node(prev, value, next);prev.next added;next.prev added;}/*** 添加到最后一个* param value 待添加值*/public void addLast(int value) {Node prev sentinel.prev;Node next sentinel;Node added new Node(prev, value, next);prev.next added;next.prev added;}/*** 删除第一个*/public void removeFirst() {Node removed sentinel.next;if (removed sentinel) {throw new IllegalArgumentException(非法);}Node a sentinel;Node b removed.next;a.next b;b.prev a;}/*** 删除最后一个*/public void removeLast() {Node removed sentinel.prev;if (removed sentinel) {throw new IllegalArgumentException(非法);}Node a removed.prev;Node b sentinel;a.next b;b.prev a;}/*** 根据值删除节点* p假定 value 在链表中作为 key, 有唯一性/p* param value 待删除值*/public void removeByValue(int value) {Node removed findNodeByValue(value);if (removed ! null) {Node prev removed.prev;Node next removed.next;prev.next next;next.prev prev;}}private Node findNodeByValue(int value) {Node p sentinel.next;while (p ! sentinel) {if (p.value value) {return p;}p p.next;}return null;}}六.解题模版
1.反转链表再正向遍历
可以先将链表反转然后正向遍历即可实现从后往前遍历。这种方法的时间复杂度为 O(N)其中 N 为链表的长度。
CLASS LISTNODE:DEF __INIT__(SELF, VAL0, NEXTNONE):SELF.VAL VALSELF.NEXT NEXT
DEF REVERSELIST(HEAD):PREV, CURR NONE, HEADWHILE CURR:NEXT_NODE CURR.NEXTCURR.NEXT PREVPREV CURRCURR NEXT_NODERETURN PREVDEF TRAVERSELIST(HEAD):NEW_HEAD REVERSELIST(HEAD)WHILE NEW_HEAD:PRINT(NEW_HEAD.VAL)NEW_HEAD NEW_HEAD.NEXT2.递归遍历
可以使用递归的方式遍历链表每次遍历到链表末尾时再开始输出节点的值。这种方法的时间复杂度也为 O(N)其中 N 为链表的长度。
CLASS LISTNODE:DEF __INIT__(SELF, VAL0, NEXTNONE):SELF.VAL VALSELF.NEXT NEXTDEF TRAVERSELIST(HEAD):IF NOT HEAD:RETURNTRAVERSELIST(HEAD.NEXT)PRINT(HEAD.VAL)需要注意的是递归遍历链表时如果链表过长可能会导致递归层数过深从而出现栈溢出的情况。因此如果链表长度较大建议使用反转链表再正向遍历的方法。
七.链表题目
1.两数相加 给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。 请你将两个数相加并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外这两个数都不会以 0 开头。 示例 1 输入l1 [2,4,3], l2 [5,6,4]
输出[7,0,8]
解释342 465 807.示例 2
输入l1 [0], l2 [0]
输出[0]示例 3
输入l1 [9,9,9,9,9,9,9], l2 [9,9,9,9]
输出[8,9,9,9,0,0,0,1]题解:
具体实现步骤如下
首先我们需要创建一个新的链表用来存储两个链表相加的结果。同时我们需要定义一个指针用来遍历链表。接着我们可以从两个链表的头节点开始依次遍历它们的每一个节点将它们对应位置的数字相加并记录进位。如果其中一个链表已经遍历结束我们就可以直接将另一个链表剩余的部分接到结果链表的后面注意这里还需要考虑进位。最后如果遍历完成后还有进位我们就需要在结果链表的末尾添加一个新节点存储进位。
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]:链表遍历:param l1::param l2::return:res ListNode(0)cur rescarry 0while l1 or l2:x l1.val if l1 else 0y l2.val if l2 else 0s x y carrycarry s // 10cur.next ListNode(s % 10)cur cur.nextif l1:l1 l1.nextif l2:l2 l2.nextif carry:cur.next ListNode(carry)return res.next时间复杂度O(max(m, n))其中 m 和 n 分别是 l1 和 l2 的长度。
空间复杂度O(max(m, n))我们需要使用一个链表来存储结果。
2.两数相加 II 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 你可以假设除了数字 0 之外这两个数字都不会以零开头。 示例 1 输入l1 [7,2,4,3], l2 [5,6,4]
输出[7,8,0,7]示例 2
输入l1 [2,4,3], l2 [5,6,4]
输出[8,0,7]示例 3
输入l1 [0], l2 [0]
输出[0]题解:
解题思路
先把两个链表逆序使得最低位在链表头部这样就可以从头部开始相加了。定义一个 carry 变量表示进位初始值为 0。定义一个新的链表 dummyHead表示相加的结果。从链表 1 和链表 2 的头部开始遍历对于每一位进行相加同时加上进位 carry。如果当前的和大于等于 10就需要进位将 carry 变为 1同时将和减去 10。将当前的和插入到新的链表 dummyHead 的末尾。遍历完链表 1 和链表 2 后如果进位 carry 为 1还需要将 carry 插入到 dummyHead 的末尾。最后将 dummyHead 逆序得到正常的结果链表。
class ListNode:def __init__(self, val0, nextNone):self.val valself.next next# 翻转链表
def reverseList(head: ListNode) - ListNode:pre Nonecurr headwhile curr:next curr.nextcurr.next prepre currcurr nextreturn preclass Solution:def addTwoNumbers(self, l11: Optional[ListNode], l22: Optional[ListNode]) - Optional[ListNode]:l1 reverseList(l11)l2 reverseList(l22)res ListNode(0)cur rescarry 0while l1 or l2:x l1.val if l1 else 0y l2.val if l2 else 0s x y carrycarry s // 10cur.next ListNode(s % 10)cur cur.nextif l1:l1 l1.nextif l2:l2 l2.nextif carry:cur.next ListNode(carry)return reverseList(res.next)3.合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 输入l1 [1,2,4], l2 [1,3,4]
输出[1,1,2,3,4,4]示例 2
输入l1 [], l2 []
输出[]示例 3
输入l1 [], l2 [0]
输出[0]题解:
要合并两个有序链表可以使用递归或迭代的方法。下面是使用迭代的方法实现合并两个有序链表的 Python 代码示例
pythonCopy code
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextdef mergeTwoLists(l1, l2):# 创建一个哑节点(dummy node)作为合并后链表的头节点dummy ListNode(0)# 创建一个指针指向合并后链表的当前节点current dummy# 循环比较l1和l2的节点值并将较小的节点添加到合并后链表中while l1 and l2:if l1.val l2.val:current.next l1l1 l1.nextelse:current.next l2l2 l2.nextcurrent current.next# 处理剩余的节点current.next l1 if l1 else l2# 返回合并后链表的头节点的下一个节点即去除哑节点return dummy.next这段代码中我们创建了一个哑节点(dummy node)作为合并后链表的头节点。然后使用一个指针current指向合并后链表的当前节点。在循环中我们比较l1和l2的节点值并将较小的节点添加到合并后链表中同时移动相应的指针。最后我们处理剩余的节点将其添加到合并后链表的尾部。最后返回合并后链表的头节点的下一个节点即去除哑节点。
你可以调用mergeTwoLists函数传入两个有序链表的头节点然后它将返回合并后的有序链表的头节点。
4.删除排序链表中的重复元素 给定一个已排序的链表的头 head 删除所有重复的元素使每个元素只出现一次 。返回 已排序的链表 。 示例 1 输入head [1,1,2]
输出[1,2]示例 2 输入head [1,1,2,3,3]
输出[1,2,3]题解:
class Solution:def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]:dummy headwhile dummy and dummy.next:# 如果当前节点和下一个节点的值相同删除下一个节点if dummy.val dummy.next.val:dummy.next dummy.next.nextelse:dummy dummy.nextreturn head5.环形链表 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 输入head [3,2,0,-4], pos 1
输出true
解释链表中有一个环其尾部连接到第二个节点。题解:
class Solution:def hasCycle(self, head: Optional[ListNode]) - bool:双指针,一个快指针,一个慢指针,如果有环 一定会相聚:param head::return:if head is None or head.next is None:return Falseslow headfast head.nextwhile slow ! fast:if fast is None or fast.next is None:return Falseslow slow.nextfast fast.next.nextreturn True6.相交链表 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 图示两个链表在节点 c1 开始相交**** 题目数据 保证 整个链式结构中不存在环。 注意函数返回结果后链表必须 保持其原始结构 。 自定义评测 评测系统 的输入如下你设计的程序 不适用 此输入 intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0listA - 第一个链表listB - 第二个链表skipA - 在 listA 中从头节点开始跳到交叉节点的节点数skipB - 在 listB 中从头节点开始跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点那么你的解决方案将被 视作正确答案 。 示例 1 输入intersectVal 8, listA [4,1,8,4,5], listB [5,6,1,8,4,5], skipA 2, skipB 3
输出Intersected at 8
解释相交节点的值为 8 注意如果两个链表相交则不能为 0。
从各自的表头开始算起链表 A 为 [4,1,8,4,5]链表 B 为 [5,6,1,8,4,5]。
在 A 中相交节点前有 2 个节点在 B 中相交节点前有 3 个节点。
— 请注意相交节点的值不为 1因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说它们在内存中指向两个不同的位置而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点B 中第四个节点) 在内存中指向相同的位置。题解:
class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) - Optional[ListNode]:思路:如果存在交点,则肯定在两个链表分别遍历对方时相交:param headA::param headB::return:if not headA or not headB:return NonenodeA, nodeB headA, headBwhile nodeA ! nodeB:nodeA nodeA.next if nodeA else headBnodeB nodeB.next if nodeB else headAreturn nodeA7.移除链表元素 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val 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
输出[]题解:
class Solution:def removeElements(self, head: Optional[ListNode], val: int) - Optional[ListNode]:链表的合适是操作2个节点,前驱和后继:param head::param val::return:# 处理头部节点while head and head.val val:head head.next# 处理非头部cur headwhile cur and cur.next:if cur.next.val val:cur.next cur.next.nextelse:cur cur.nextreturn head8.反转链表 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 示例 1 输入head [1,2,3,4,5]
输出[5,4,3,2,1]示例 2 输入head [1,2]
输出[2,1]示例 3
输入head []
输出[]题解:
class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:反转链表:定义前节点和当前节点:param head::return:pre, curr None, headwhile curr is not None:next curr.nextcurr.next prepre currcurr nextreturn pre9.回文链表 给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。 输入head [1,2,2,1]
输出true题解:
class Solution:def isPalindrome(self, head: Optional[ListNode]) - bool:回文链表:param head::return:contain []curr headwhile curr is not None:contain.append(curr.val)curr curr.nextcurr2 headwhile curr2 is not None:if contain.pop() ! curr2.val:return Falsecurr2 curr2.nextreturn True10.链表的中间结点 给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 输入head [1,2,3,4,5]
输出[3,4,5]
解释链表只有一个中间结点值为 3 。题解:
class Solution:def middleNode(self, head: Optional[ListNode]) - Optional[ListNode]:链表的中间结点,如果有2个 返回第二个 快慢指针:param head::return:fast, slow head, headwhile fast is not None and fast.next is not None:slow slow.nextfast fast.next.nextreturn slow觉得有用的话点个赞 呗。 ❤️❤️❤️本人水平有限如有纰漏欢迎各位大佬评论批评指正 如果觉得这篇文对你有帮助的话也请给个点赞、收藏下吧非常感谢! Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧
