摸鱼学大师

题解

未归档(8)

/ 注册

全部文章 / 题解（共23篇）

题解 | #划分链表# 来自专栏

题目的主要信息：给出一个长度为 n 的单链表和一个值 x 返回一个链表的头结点，要求新链表中小于 x 的节点全部在大于等于 x 的节点左侧两个部分之内的节点之间与原来的链表要保持相对顺序不变进阶要求：时间复杂度 O(n)O(n)O(n) ，空间复杂度 O(1)O(1)O(1) 方法一：两...

C++ 链表

2021-12-06

0 395

题解 | #链表内指定区间反转# 来自专栏

题目的主要信息：将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转进阶要求：时间复杂度 O(n)O(n)O(n)，空间复杂度 O(1)O(1)O(1) 方法一：递归具体做法：如果m == 1,就相当于反转链表的前 n 元素；如果 m != 1我们把 head 的索引视为...

C++ 链表递归双指针

2021-12-06

13 1241

题解 | #删除链表中重复的结点# 来自专栏

题目的主要信息：在一个非降序的链表中，存在重复的结点，删除该链表中重复的结点，重复的结点不保留进阶要求：时间复杂度：O(n)O(n)O(n)，空间复杂度：O(n)O(n)O(n) 方法一：哈希表具体做法：可以遍历一次链表用哈希表记录每个结点值出现的次数，然后在链表前加一个结点值为0的表头...

C++ 链表哈希表

2021-12-02

0 359

题解 | #两个链表的第一个公共结点# 来自专栏

题目中的信息：两个链表含有公共结点或没有，有公共结点则返回第一公共结点指针单链表，无循环没有公共节点返回空要求：时间复杂度：O(n)O(n)O(n)，空间复杂度：O(1)O(1)O(1) 方法一：双指针长度比较法具体做法：我们可以通过单独的遍历比较两个链表的长度，得到长度差n，其中较...

C++ 链表

2021-12-01

11 460

题解 | #输出单向链表中倒数第k个结点# 来自专栏

题目的主要信息：输入一个单向链表，输出该链表中倒数第k个结点链表的倒数第1个结点为链表的尾指针异常返回空指针 k为0输出0 方法一：根据长度找倒数k 具体做法：正常遍历，根据输入连接链表，一共n个值，链表长度为n。然后比较链表长度是否比k小，如果比k小返回一个空链表，否则遍历n-k次即...

C++ 链表双指针

2021-10-26

26 792

题解 | #从单向链表中删除指定值的节点# 来自专栏

题目的主要信息：输入一个单向链表和一个节点的值，从单向链表中删除等于该值的节点，删除后如果链表中无节点则返回空指针构造链表的过程，第一个输入n表示链表长度，第二个输入时头节点值，后续n-1对输入，每对输入第一个数表示要输入的值，第二个数表示要输入的值前一个位置的值链表中的值都不相同方法一...

C++ 链表

2021-10-25

17 936

题解 | #两个链表的第一个公共结点# 来自专栏

题目的主要信息：两个无环的单向链表，找出它们的第一个公共结点如果没有公共节点则返回空要求：空间复杂度O(1)O(1)O(1)，时间复杂度O(n)O(n)O(n) 方法一：长度比较法具体做法：我们可以分别统计两个链表的长度，然后对于较长的一个链表先走长度之差这么多步，在同步往后遍历，遇到...

双指针链表 Java

2021-10-02

13 710

题解 | #反转链表# 来自专栏

题目的主要信息：给定一个长度为nnn的链表，反转该链表，输出表头要求：时间复杂度为O(n)O(n)O(n)，空间复杂度为O(1)O(1)O(1) 方法一：递归（能过，空间不符合要求）具体做法：我们可以利用递归的反向工作来实现逆转。对于每个结点我们递归向下遍历到最后，然后往上依次逆转两个结...

C++ 链表

2021-10-01

0 406

题解 | #链表中倒数最后k个结点# 来自专栏

题目的主要信息：一个长度为nnn的链表，返回原链表中从倒数第k个结点至尾节点的全部节点如果该链表长度小于k，请返回一个长度为 0 的链表要求：时间复杂度O(n)O(n)O(n)，空间复杂度O(n)O(n)O(n)，进阶要求空间复杂度O(1)O(1)O(1) 方法一：先找长度再找最后k 具体...

C++ 双指针链表

2021-10-01

0 418

题解 | #从尾到头打印链表# 来自专栏

题目的主要信息：输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值返回值保存在vector的数组中方法一：递归具体做法：我们都知道递归到底层后才会往上，因此我们可以递归遍历链表，将填充数组放到递归函数后面，就可以实现遍历到链表最后再逐渐往前将值填到数组中。 class Solut...

C++ 递归链表栈

2021-09-29

0 361