链表总结
链表的总结
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。 —wiki
单向链表
链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值。
单向链表的基本操作
1 |
|
插入操作
在某个节点以后插入一个节点
1 | //将s节点插入到第i个位置 |
前插操作
扩展:对某一结点进行前插操作
前插操作是指在某结点的前面插入一个新结点,后插操作的定义刚好与之相反,在单链表插入算法中,通常都是釆用后插操作的。
以上面的算法为例,首先调用函数GetElem()找到第i-1个结点,即待插入结点的前驱结点后,再对其执行后插操作。由此可知,对结点的前插操作均可以转化为后插操作,前提是从单链表的头结点开始顺序查找到其前驱结点,时间复杂度为O(n)。
此外,可以釆用另一种方式将其转化为后插操作来实现,设待插入结点为s,将插入到p的前面。我们仍然将s插入到p的后面,然后将p->data与s->data交换即可,这样既满足了逻辑关系,又能使得时间复杂度为O(1)。算法的代码片段如下:
1 | //将结点插入到*P之前的主要代码片段 |
删除操作和求表长
双向链表
wiki中实现的双向链表
此时,双向链表的头结点不放任何数据,只作索引作用(终止作用),这时的双向链表是循环的,最后一个节点的next指针指向头结点,头结点的prev指针指向最后一个节点
循环链表
链表的相关面试题
Reverse Linked List
利用头插法翻转链表
1 | class Solution { |
Reverse Linked List II
反转特定区间的节点
解体思路:记住开始反转的节点start, 它的前一个节点prev, 则就转为将prev->start->temp(start->next)变成prev->temp->start,即将start的后一个节点循环加入到start的前面,插入后start指向它的下下一个节点。
1 | class Solution { |
Rotate List
解体思路:题目是将右移,可以把它变成循环链表,移完后再记录下当前的头结点和尾节点,再拆分,此处需要注意的是当k大于链表的长度的时候,相当于对链表长度的余数
1 | /** |
Copy List with Random Pointer
解法一:新构造一个链表,复制原有链表的label,但是在给新的链表的随机指针(random)赋值时,每次都需要重新遍历一遍原有的链表,来确定随机指针指向的节点(或NULL),可以使用hash表来解决上述查询问题,建立原有节点到现节点的map,这样在查找新链表的随机指针时,找到原有节点的随机指针的指向,在根据这个地址来寻找它在新链表的位置,
这会额外使用O(n)的map空间
第一步:使用HashMap,首先复制所有的节点,用HashMap记录老节点A与新节点A’的映射关系。
第二步:遍历每个点,将Random指针连上。如存在一条Random指针从A指向B,那么在HashMap中找到映射的新节点A’和B’,将A’的Random指针指向B’。
1 | /** |
解法二:(1)将每个节点的复制节点插入到它的后面
(2)更新新插入节点的随机指针
(3)分离两个链表
第一步:将每个节点复制并插入相邻节点中。如1->2->3->NULL变为:1->1’->2->2’->3->3’->NULL。
第二步:接下来连接Random指针,如果存在一条Random指针从A指向B,那么将A->next的Random指针指向B->next。
第三步:将链表拆开。A=head, A’=head->next; A->next=A->next->next;A’->next=A’->next->next; …
1 | /** |
Sort List
解体思路:首先题目规定的时间为$O(n log n)$,那么首先想到的就是归并排序了
(1)要归并,首先得求链表的中点,在中点处将链表断开
(2)合并两个已经排好序的链表
求链表的中点
1 | /* |
完整代码
1 | /** |