首先我们从反转链表这个经典问题开始。
经典问题 - 反转链表
解决方案是按原始顺序迭代节点,将它们逐个移动到列表的头部,用一个例子来说明这个算法。
算法概述
例子如下: 23 -> 6 -> 15 -> Ø,节点 23 是原始的头节点。
- 首先,我们将节点 6 移动到列表的头部;
- 然后,我们将节点 15 移动到列表的头部;
- 现在节点 23 的下一个节点是空。因此,我们停止这一过程并返回头节点 15。
更多
在该算法中,每个节点只移动一次,因此,时间复杂度为 _O(N)_,其中 N 是链表的长度。
只使用了常量级的额外空间,所以空间复杂度为 _O(1)_。
这个问题是在面试中可能遇到的许多链表问题的基础。
还有其他的解决方案,您应该熟悉至少一个解决方案并能够实现它。
题目:反转链表
要求反转一个单链表
示例:
1 | 输入: 1->2->3->4->5->NULL |
进阶:使用迭代或递归两种方法反转链表。
迭代方法
个人理解:
假设链表为 1 -> 2 -> 3 -> Ø,我们要改成 1 <- 2 <- 3 <- Ø
在遍历链表时,将当前节点的 next 指向上一个元素。由于单链表没有上一个节点,因此必须实现存储上一个节点。
在更改引用之前,还需要另一个指针来存储下一个节点。
代码如下(C++):
1 | class Solution { |
递归方法
个人理解:
参考 路漫漫我不畏的相关题解,写的很好。
- 使用递归函数,一直递归到链表的最后一个节点,该节点就是反转后的头节点,记作 ret;
- 此后,每次函数在返回的过程中,让当前节点的下一个节点的 next 指针指向当前节点;
- 同时让当前节点的 next 指针指向 NULL,从而实现从链表尾部开始的局部反转;
- 当递归全部出栈后,链表反转完成。
代码如下(C++):
1 | class Solution { |
题目:移除链表元素
删除链表中等于给定值 val 的所有节点。
示例:
1 | 输入: 1->2->6->3->4->5->6, val = 6 |
个人理解:
链表内部,等于 val 就删掉,对于链表来说,那节点值如果等于 val 则将节点前指向节点后即可。
关键问题在于,如何处理头和尾部,这里我们引入哨兵节点。
哨兵节点广泛应用于树和链表中,如伪头、伪尾、标记等,它们是纯功能的,通常不保存任何数据,其主要目的是使链表标准化,例如:使链表永不为空、永不无头、简化插入和删除。
- 初始化哨兵节点为 ListNode(0)并设置其 next 指向 head
- 初始化 curr 和 prev 指向当前节点和前继节点
- 当 curr != nullptr
- 比较当前节点和要删除的节点
- 若是,则 prev -> next = curr -> next;
- 否则,prev = curr;
- 遍历下一个元素:curr = curr -> next;
- 比较当前节点和要删除的节点
- 返回 sentinel -> next
代码如下(C++):
1 | class Solution { |
题目:奇偶链表
给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 _O(1)_,时间复杂度应为 _O(nodes)_,nodes 为节点总数。
示例:
1 | 输入: 1->2->3->4->5->NULL |
说明:
- 应当保持奇数节点和偶数节点的相对顺序。
- 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。
个人理解:
设定多个指针,head 为奇指针头部,odd 为奇指针,evenHead 为偶指针头部,even 为偶指针。
将奇节点放在一个链表内,将偶节点放在一个列表内,最后将偶节点连接到奇节点尾部。
详解:
- 首先 odd 和 head 指向奇头部,evenHead 和 even 指向偶头部;
- 修改 odd next 指针的指向,指向 odd -> next -> next,即 odd -> next = odd -> next -> next;
- 然后将 odd 向后移动一位;
- 再操作 even 的 next 指针指向,如下:even -> next = even -> next -> next;
- 移动 even,以 even 作为结束条件;
- 拼接 odd -> next = evenHead。
代码如下(C++):
1 | class Solution { |
test
题目:回文链表
请判断一个链表是否为回文链表。
示例:
1 | 输入: 1->2 |
进阶:使用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题。
个人理解:
将链表内容复制到容器中,对容器中的内容进行循环遍历即可。
代码如下(C++):
1 | class Solution { |
进阶方法,官方提供了思路:
改变输入。将链表的后半部分反转(修改链表结构),然后将后半部分与前半部分比较。比较之后需要将链表恢复。
算法步骤:
- 找到前半部分链表的尾节点。
- 反转后半部分链表
- 判断是否回文
- 恢复链表
进阶代码如下:
参考hello_pretty
1 | class Solution { |
小结 - 链表经典问题
通过练习可以找到一些链表问题的相似之处。
1.通过一些测试用例可以节省您的时间。
使用链表时不易调试。因此,在编写代码之前,自己尝试几个不同的示例来验证您的算法总是很有用的。
2.你可以同时使用多个指针。
有时,当你为链表问题设计算法时,可能需要同时跟踪多个结点。您应该记住需要跟踪哪些结点,并且可以自由地使用几个不同的结点指针来同时跟踪这些结点。
如果你使用多个指针,最好为它们指定适当的名称,以防将来必须调试或检查代码。
3.在许多情况下,你需要跟踪当前结点的前一个结点。
你无法追溯单链表中的前一个结点。因此,您不仅要存储当前结点,还要存储前一个结点。这在双链表中是不同的。
声明:本文为学习记录,不做商业用途,如果有侵权内容,请联系我立即删除。