【OJ-0x0001-Leetcode】单向链表部分write-up-by-arttnba3

0x00.绪论

leetcode上面的链表题很有意思,最近做到我废寝忘食都写不出来,所以推荐大家都去写一写(逃

说实话双向链表比单向链表方便的太多了(笑),这点空间复杂度不算什么,建议大家都去写双向链表(不)

不过其实相对于空间复杂度,我更看重时间复杂度,空间复杂度再高一般也不容易爆,然而时间复杂度稍微高一点点往往就容易TLE…(来自OI狗的怨念)

顺便作为大括号换行党吐槽一下Leetcode的不换行机制😡

注:因为题是写不完的,所以这篇文章会不定期的进行更新www

最后一次更新日期为:2020.4.23(终于等来的更新?

Pre:单向链表构造方式

如下,对链表不了解的可以康康我先前写的关于链表的博文

1
2
3
4
typedef struct ListNode{
int val;//该节点的值,也可以是其他类型甚至是多个变量
struct ListNode*next;//指向下一节点的指针
}LN;//通过typedef以达到使用新关键字LN声明ListNode类型结构体变量的目的

(大概长这个样子)
在这里插入图片描述

0x01.两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

Talk is cheap. Show me the code.其实是因为我懒并且写完也看不懂了

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
int num,num2,pd=0;//pd为进位标识符
struct ListNode* temp=(struct ListNode*)malloc(sizeof(struct ListNode));
temp->val=0;
temp->next=NULL;
struct ListNode* temp2=temp;
while(true)//对两个链表进行遍历,模拟整数加减法
{
num=0;
if(l1==NULL&&l2==NULL)//都遍历完了
{
if(pd==1)//进行最后一次计算
;
else
break;
}
else if(l1==NULL)//l1先于l2结束遍历
{
num=l2->val;
l2=l2->next;
}
else if(l2==NULL)//l2先于l1结束遍历
{
num=l1->val;
l1=l1->next;
}

else//常规运算
{
num=l1->val+l2->val;
l1=l1->next;
l2=l2->next;
}
if(pd)//重置pd
{
num+=num2;
pd=0;
}
if(num>9)//进位
{
pd=1;
num2=num/10;
num%=10;
}
temp->val=num;
if(l1==NULL&&l2==NULL&&pd==0)
break;
//分配新的节点进行接续,模拟数组
struct ListNode* temp3=(struct ListNode*)malloc(sizeof(struct ListNode));
//节点赋值
temp3->next=NULL;
temp->next=temp3;
temp=temp3;
}
return temp2;
}

在这里插入图片描述

0x02.删除链表中的节点

请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

现有一个链表 – head = [4,5,1,9],它可以表示为:

示例 1:

输入: head = [4,5,1,9], node = 5 输出: [4,1,9] 解释: 给定你链表中值为 5
的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9. 示例 2:

输入: head = [4,5,1,9], node = 1 输出: [4,5,9] 解释: 给定你链表中值为 1
的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

说明:

链表至少包含两个节点。 链表中所有节点的值都是唯一的。 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/delete-node-in-a-linked-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题目当中只给你一个节点,就是要删除的节点,但是在一个单向链表当中,你无法知道这个节点的上一个节点的地址,如何删除?

只要把这个节点变成自己的下一个节点就好了嘛www

注意:在leetcode上面提交时虽然不能使用free()释放被替换节点的内存,但是在实际写删除节点的代码时一定要注意及时释放内存!

注意2:题目虽然保证了输入的绝对合法性,但是在实际写代码时永远不要相信用户的输入!

1
2
3
4
void deleteNode(struct ListNode* node) {
node->val=node->next->val;
node->next=node->next->next;
}

在这里插入图片描述

这么简短的代码还会有那么高的空间复杂度……?

0x03.删除链表的倒数第n个节点

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

用一个数组存储每一个节点的地址,我觉得彳亍,并且完成了进阶解法仅扫描一遍的要求

但是有个缺点就是不能够应对任意长度的链表的情况

使用C++中的vector容器或许可以解决数组固定长度的问题?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
struct ListNode * fptr;
struct ListNode *temp[100];
fptr=head;
if(head==NULL)
return head;
int l_list;
for(l_list=0;fptr!=NULL;l_list++)
{
temp[l_list]=fptr;
fptr=fptr->next;
}
if(n==l_list)
return head->next;
temp[l_list-n-1]->next=temp[l_list-n]->next;
return head;
}

在这里插入图片描述

0x04.反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

迭代法

说实话一开始我想的是像数组一样进行交换,但是那样会很麻烦并且时间复杂度会很高,空间复杂度甚至会翻倍

后面看了看大佬的博文,想到可以对这个单向链表进行重构

重新将这个单向链表构造成其反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct ListNode* reverseList(struct ListNode* head){
if(head==NULL||head->next==NULL)
return head;

struct ListNode* ptr1 = head, *ptr2 = head->next, *temp;
ptr1->next=NULL;//reset it as the final node
while(ptr2!=NULL)
{
//注释以第一次构造为例进行说明
temp=ptr2->next;//储存3号节点
ptr2->next=ptr1;//2号节点指向1号节点
ptr1=ptr2;//1号节点变为2号节点(待指向节点)
ptr2=temp;//2号节点变为3号节点(下一次循环的流程将会使3号指向2号)
}
return ptr1;
}

在这里插入图片描述

递归法

基本思路其实是和迭代法是一样的,都是对链表进行重构

使用函数递归找到最后一个节点使其成为第一个节点后开始进行重构

缺点就是递归会占用大量的栈空间

代码如下:

1
2
3
4
5
6
7
8
9
10
11
struct ListNode* reverseList(struct ListNode* head)
{
if(head==NULL||head->next==NULL)
return head;

struct ListNode * newhead = reverseList(head->next);//从后往前遍历每个节点
head->next->next = head;//将当前节点的后一个节点的 next 指向当前结点
head->next = NULL;//断开当前节点指向后一个节点

return newhead;
}

在这里插入图片描述

0x05.回文链表

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

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶: 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

高空间复杂度的解法一:构建一个反向的单向链表再进行对比(一拍脑门直接想出来的解法XD

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
bool isPalindrome(struct ListNode* head){
int i=0,j;
typedef struct sptr {
struct sptr *last;
struct ListNode *ptrn;
}sPtr;
struct ListNode *ptr=head;
sPtr *temp,*temp2=NULL;
while(ptr!=NULL)
{
temp=(sPtr*)malloc(sizeof(sPtr));
temp->last=NULL;
if(temp2!=NULL)
temp->last=temp2;
temp->ptrn=ptr;
ptr=ptr->next;
i++;
if(ptr!=NULL)
temp2=temp;
}
for(j=0;j<i/2;j++)
{
if(head->val!=temp->ptrn->val)
return false;
head=head->next;
temp=temp->last;
}
return true;
}

很显然,最终的结果惨不忍睹
在这里插入图片描述

进阶解法:快慢指针&链表反转

概念:快慢指针

快慢指针为链表题里用的挺多的一个小技巧

当我们在遍历一个链表的时候,我们可以使用两个指针进行遍历,一个步长为1(为慢指针),一个步长为2(为快指针),这样当快指针走到链表尾的时候,慢指针刚好走到链表的中段

简单的代码实现如下:

1
2
3
4
5
6
7
8
struct ListNode* sptr, *fptr;//slow pointer and fast pointer
int l_list;
for(l_list=0;sptr!=NULL;l_list++)
{
if(l_list%2)
sptr=sptr->next;
fptr=fptr->next;
}

那么我们在判断一个链表是否为回文链表的时候,我们可以选择使用快慢指针对链表进行一次遍历,再将前半部分链表进行反转,之后从头指针开始配合使用慢指针同步对比前后半部分是否相同

反转链表的实现方法在前文已经讲过了,不再做过多解析

最终的代码实现如下:

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
34
35
36
37
38
39
40
41
42
bool isPalindrome(struct ListNode* head)
{
if(head==NULL||head->next==NULL)
return true;
if(head->next->next==NULL)
{
if(head->val==head->next->val)
return true;
return false;
}
struct ListNode * fptr, *sptr, *temp, *temp2, *ptr1, *ptr2;
int l_list,i;
fptr=sptr=head;
for(l_list=0;fptr!=NULL;l_list++)
{
if(l_list%2)
sptr=sptr->next;
fptr=fptr->next;
}
ptr1=head;
ptr2=head->next;
ptr1->next=sptr;
while(ptr2!=sptr)
{
temp2=ptr2->next;
ptr2->next=ptr1;
ptr1=ptr2;
ptr2=temp2;
}
head=ptr1;
if(l_list%2)
sptr=sptr->next;
l_list/=2;
for(i=0;i<l_list;i++)
{
if(head->val!=sptr->val)
return false;
head=head->next;
sptr=sptr->next;
}
return true;
}

在这里插入图片描述

0x06.反转链表II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一趟扫描进行完成,说实话属实有点麻烦,并且还指定了要反转的位置…

等等,制定了要反转的位置?

那么只要我们在遍历到那个位置的时候进行反转不就好了嘛www

思路:在需要反转的位置重新构建一条新的反转后的链表,构建结束后将其重新嵌入原来的位置

大致是下面的这样一个流程:

原始数据: [1,2,3,4,5] 反转位置:2~4

第一趟循环:1->2->3->4->5 操作:无

第二趟循环:1->3->2->4->5 操作:3->2, 2->4, 1->3

第三趟循环:1->4->3->2->5 操作:4->3, 2->5, 1->4

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
34
35
36
37
struct ListNode* reverseBetween(struct ListNode* head, int start, int end)
{
if(start == end)
return head;
struct ListNode *returnNode = head, *ergodic = head, *newHead = head, *temp;
/*
* ergodic: 当前正在遍历的节点
* temp: 反转前ergodic的下一节点
* newHead: 反转开始位置的上一节点,若从第一个节点开始反转则恒为第一个节点
* returnNode: 最后形成的整个链表的第一个节点
*/
for(int i=1;i<end;i++)
{
if(start <= i)
{
temp = ergodic->next;
ergodic->next = temp->next;
if(start!=1)//反转从中间开始
{
temp->next=newHead->next;
newHead->next = temp;
}
else//从头开始反转,需要时刻变更头节点
{
temp->next = newHead;
newHead = returnNode = temp;
}

}
else
{
newHead = ergodic;
ergodic = ergodic->next;
}
}
return returnNode;
}

QQ截图20200423020827.png

0x07.二叉树中的链表

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中,存在一条一直向下的路径,且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值,那么请你返回 True,否则返回 False

一直向下的路径的意思是:从树中某个节点开始,一直连续向下的路径。

示例 1:

输入:head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出:true
解释:树中蓝色的节点构成了与链表对应的子路径。

示例 2:

输入:head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出:true

示例 3:

输入:head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出:false
解释:二叉树中不存在一一对应链表的路径。

提示:

二叉树和链表中的每个节点的值都满足 1 <= node.val <= 100 。
链表包含的节点数目在 1 到 100 之间。
二叉树包含的节点数目在 1 到 2500 之间。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/linked-list-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这题咋一看很难的样子,其实仔细一想,这不就是我们常用的递归算法中的二叉树的前序遍历🐎,一股熟悉的感觉扑面而来www

前序遍历:先遍历根节点,再遍历左节点,再遍历又节点

不熟悉递归算法的可以先看看我以前的博文,然后把OpenJudge.1700:八皇后问题给做了,那么这道题的算法你基本上也就该明白了

思路:递归前序遍历二叉树查找对应的"链表",找到了直接返回True,遍历完整棵树都没找到则返回False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool seek(struct ListNode* head, struct TreeNode* root)//此函数进行对比
{
if(head == NULL)//链表遍历完了,直接true
return true;
if(root == NULL)//链表没完树先到头肯定是false
return false;
if(head->val!=root->val)//遍历到一半不一样,肯定是false
return false;
return seek(head->next,root->left)||seek(head->next,root->right);
}


bool isSubPath(struct ListNode* head, struct TreeNode* root)//此函数仅用作开始对比的入口
{
if(root == NULL)
return false;
return seek(head,root)||isSubPath(head,root->left)||isSubPath(head,root->right);//根节点||左孩子做根节点||右孩子做根节点
}

QQ截图20200423032409.png

0x08.合并K个排序链表

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

Leetcode链表题当中唯二的两道难度为困难的题之一,看起来似乎并不难的样子,似乎只需要多次遍历拼接得到一个新的链表就好了

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
34
35
36
37
38
39
40
41
42
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
if(listsSize == 0)
return NULL;
else if(listsSize == 1)
return lists[0];
//以上为处理特殊情况
struct ListNode* head = NULL, *temp;//要返回的新链表的头和遍历变量
int pd;
for(int i=0;i<listsSize;)
{
int min = 9999999;
pd = -1;
for(int j=0;j<listsSize;j++)
{
if(lists[j]!=NULL)
{
if(lists[j]->val<=min)
{
min=lists[j]->val;
pd = j;
}
}
}
if(pd == -1)
return head;//都空了的情况
if(head == NULL)//单独处理头
{
head = temp = lists[pd];
lists[pd] = lists[pd]->next;
}
else
{
temp->next = lists[pd];
temp = temp->next;
lists[pd] = lists[pd]->next;
}
if(lists[pd] == NULL)
i++;
}
return head;
}

QQ截图20200423104733.png

毫无疑问,这个拍脑门想出来的算法的时间复杂度极高XD

那么我们应该如何进行优化呢?

咕了,后面再补

0x09.K 个一组翻转链表

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

示例:

给你这个链表:1->2->3->4->5

当 k = 2 时,应当返回:2->1->4->3->5

当 k = 3 时,应当返回: 3->2->1->4->5

说明:

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换

PS:指不能偷懒吗XDDD

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

Leetcode链表题当中唯二的两道难度为困难的题之二,确实挺有分量

但是既然我们都做了两道链表反转了,那么这题其实我们是可以使用类似的思路的XD

鸽了,下次再写