Aelous-Blog

养一猫一狗,猫叫夜宵,狗叫宵夜

0%

链表-03

首先我们从反转链表这个经典问题开始。

经典问题 - 反转链表

解决方案是按原始顺序迭代节点,将它们逐个移动到列表的头部,用一个例子来说明这个算法。

算法概述

例子如下: 23 -> 6 -> 15 -> Ø,节点 23 是原始的头节点。

  1. 首先,我们将节点 6 移动到列表的头部;
  2. 然后,我们将节点 15 移动到列表的头部;
  3. 现在节点 23 的下一个节点是空。因此,我们停止这一过程并返回头节点 15。

更多

在该算法中,每个节点只移动一次,因此,时间复杂度为 _O(N)_,其中 N 是链表的长度。
只使用了常量级的额外空间,所以空间复杂度为 _O(1)_。

这个问题是在面试中可能遇到的许多链表问题的基础。

还有其他的解决方案,您应该熟悉至少一个解决方案并能够实现它。

题目:反转链表

要求反转一个单链表

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:使用迭代或递归两种方法反转链表。

迭代方法

个人理解
假设链表为 1 -> 2 -> 3 -> Ø,我们要改成 1 <- 2 <- 3 <- Ø
在遍历链表时,将当前节点的 next 指向上一个元素。由于单链表没有上一个节点,因此必须实现存储上一个节点。
在更改引用之前,还需要另一个指针来存储下一个节点。

代码如下(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode * curr{head}, *prev{nullptr}; // 定义一个空的 prev 节点,以及指向头部的 curr 节点
while(curr != nullptr){
ListNode *nex = curr -> next; // 定义一个临时节点,指向 curr 的 next
curr -> next = prev; // 将 curr 的 next 指向prev
prev = curr; // 将 prev 移动到 curr
curr = nex; // 将 curr 移动到 nex
}
return prev;
}
};

递归方法

个人理解

参考 路漫漫我不畏的相关题解,写的很好。

  1. 使用递归函数,一直递归到链表的最后一个节点,该节点就是反转后的头节点,记作 ret;
  2. 此后,每次函数在返回的过程中,让当前节点的下一个节点的 next 指针指向当前节点;
  3. 同时让当前节点的 next 指针指向 NULL,从而实现从链表尾部开始的局部反转;
  4. 当递归全部出栈后,链表反转完成。

代码如下(C++):

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == nullptr || head.next == nullptr) return head;
ListNode *ret = reverseList(head -> next); // 递归掉用
head -> next -> next = head; // 递归方程,下一个指向前面
head -> next = nullptr; // 下一个指空
return ret;
}
};

题目:移除链表元素

删除链表中等于给定值 val 的所有节点。

示例:

1
2
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

个人理解
链表内部,等于 val 就删掉,对于链表来说,那节点值如果等于 val 则将节点前指向节点后即可。
关键问题在于,如何处理头和尾部,这里我们引入哨兵节点

哨兵节点广泛应用于树和链表中,如伪头、伪尾、标记等,它们是纯功能的,通常不保存任何数据,其主要目的是使链表标准化,例如:使链表永不为空永不无头简化插入和删除

  • 初始化哨兵节点为 ListNode(0)并设置其 next 指向 head
  • 初始化 curr 和 prev 指向当前节点和前继节点
  • 当 curr != nullptr
    • 比较当前节点和要删除的节点
      • 若是,则 prev -> next = curr -> next;
      • 否则,prev = curr;
    • 遍历下一个元素:curr = curr -> next;
  • 返回 sentinel -> next

代码如下(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 需要哨兵节点,也就是哑节点
ListNode *sentinel = new ListNode(0);
sentinel -> next = head;
ListNode *prev = sentinel, *curr = head, *toDelete = nullptr;
while(curr != nullptr){
if(curr -> val == val){
prev -> next = curr -> next;
toDelete = curr;
}else prev = curr;
curr = curr -> next;
if(toDelete != nullptr){
delete toDelete;
toDelete = nullptr;
}
}
ListNode *ret = sentinel -> next;
delete sentinel;
return ret;
}
};

题目:奇偶链表

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 _O(1)_,时间复杂度应为 _O(nodes)_,nodes 为节点总数。

示例:

1
2
3
4
5
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if(head == nullptr) return NULL;
ListNode *odd{head}, *evenHead{head->next}, *even{head->next};
while(even != nullptr && even->next != nullptr){
odd -> next = odd -> next -> next; // 先修改指向
odd = odd -> next; // 再移动指针
even -> next = even -> next -> next; // 先修改指向
even = even -> next; // 再移动指针
}
odd -> next = evenHead; // 拼接
return head;
}
};

test

题目:回文链表

请判断一个链表是否为回文链表。

示例:

1
2
3
4
5
输入: 1->2
输出: false

输入: 1->2->2->1
输出: true

进阶:使用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题。

个人理解
将链表内容复制到容器中,对容器中的内容进行循环遍历即可。

代码如下(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> a; // 定义容器a
while(head != nullptr){ // 将链表内容复制到a中
a.push_back(head->val);
head = head -> next;
}
for(int i = 0; i < a.size()/2; i++){ // 遍历a的前半部分
if(a[i] != a[a.size()-i-1]) return false; // 与后半部分做对比
}
return true;
}
};

进阶方法,官方提供了思路:
改变输入。将链表的后半部分反转(修改链表结构),然后将后半部分与前半部分比较。比较之后需要将链表恢复。

算法步骤:

  1. 找到前半部分链表的尾节点。
  2. 反转后半部分链表
  3. 判断是否回文
  4. 恢复链表

进阶代码如下:
参考hello_pretty

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(!head || !head->next) // 特判
return 1;
ListNode *fast = head, *slow = head;
ListNode *p, *pre = NULL;
while(fast && fast->next){
p = slow;
slow = slow->next; // 快慢遍历
fast = fast->next->next;
p->next = pre; // 翻转
pre = p;
}
if(fast) // 奇数个节点时,跳过中间节点
slow = slow->next;
while(p){ // 前半部分和后半部分比较
if(p->val != slow->val)
return 0;
p = p->next;
slow = slow->next;
}
fast = head, slow = head;
while(fast && fast->next){
p = slow;
slow = slow->next; // 快慢遍历
fast = fast->next->next;
p->next = pre; // 翻转
pre = p;
}
return 1;
}
};

小结 - 链表经典问题

通过练习可以找到一些链表问题的相似之处。

1.通过一些测试用例可以节省您的时间。

使用链表时不易调试。因此,在编写代码之前,自己尝试几个不同的示例来验证您的算法总是很有用的。

2.你可以同时使用多个指针。

有时,当你为链表问题设计算法时,可能需要同时跟踪多个结点。您应该记住需要跟踪哪些结点,并且可以自由地使用几个不同的结点指针来同时跟踪这些结点。
如果你使用多个指针,最好为它们指定适当的名称,以防将来必须调试或检查代码。

3.在许多情况下,你需要跟踪当前结点的前一个结点。

你无法追溯单链表中的前一个结点。因此,您不仅要存储当前结点,还要存储前一个结点。这在双链表中是不同的。

声明:本文为学习记录,不做商业用途,如果有侵权内容,请联系我立即删除

End~~ 撒花= ̄ω ̄=花撒
如果您读文章后有收获,可以打赏我喝咖啡哦~