目录
十、链表的带环问题(重点)
十一、顺序表和链表的区别(重点)
接下来我们会从易到难，逐步讲解有关链表的常见面试，部分题目来自Leetcode和牛客
一、移除链表元素
LeetoCode链接: 203. 移除链表元素 - 力扣（LeetCode）
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode* tail = NULL;
struct ListNode* cur = head;
head = NULL;
while(cur != NULL){
if(cur->val == val){
struct ListNode* del = cur;
cur = cur->next;
free(del);
}else{
if(tail == NULL){
head = tail = cur;
}else{
tail->next = cur;
tail = tail->next;
}
cur = cur->next;
}
}
if(tail != NULL)
tail->next = NULL;
return head;
}
二、反转链表
LeetCode链接: 206. 反转链表 - 力扣（LeetCode）
思路一:
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* cur = head;
struct ListNode* newhead = NULL;
while(cur != NULL){
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}
思路二:
struct ListNode* reverseList(struct ListNode* head){
if(head == NULL)return NULL;
struct ListNode* n1,*n2,*n3;
n1 = NULL;
n2 = head;
n3 = n2->next;
while(n2 != NULL){
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3)
n3 = n3->next;
}
return n1;
}
三、链表的中间结点
LeetCode链接: 876. 链表的中间结点 - 力扣（LeetCode）
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow = head,*fast = head;
while(fast != NULL&& fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}四、链表中倒数第k个结点
牛客网链接: 链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
if(pListHead == NULL || k == 0) return NULL;
struct ListNode* slow = pListHead , *fast = pListHead;
for(int i = 0;i < k ;++i){
if(fast == NULL) return NULL;
fast = fast->next;
}
while(fast != NULL){
fast = fast->next;
slow = slow->next;
}
return slow;
}五、合并两个有序链表
LeetCode链接: 21. 合并两个有序链表 - 力扣（LeetCode）
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
struct ListNode* head,*tail;
head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
tail->next = NULL;
while (list1 != NULL && list2 != NULL) {
if (list1->val < list2->val) {
tail->next = list1;
list1 = list1->next;
}
else {//list1->val >= list2->val
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
if (list1 != NULL)
tail->next = list1;
if (list2 != NULL)
tail->next = list2;
struct ListNode* del = head;
head = head->next;
free(del);
return head;
}六、链表分割
牛客网链接: 链表分割_牛客题霸_牛客网
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode* less_head,*less_tail;
less_head = less_tail = (struct ListNode*)malloc(sizeof(struct ListNode));
less_tail->next = NULL;
struct ListNode* greater_head,* greater_tail;
greater_head = greater_tail = (struct ListNode*)malloc(sizeof(struct ListNode*));
greater_tail->next = NULL;
struct ListNode* current = pHead;
while(current != NULL){
if(current->val < x){
less_tail->next = current;
less_tail = less_tail->next;
}
else{
greater_tail->next = current;
greater_tail = greater_tail->next;
}
current = current->next;
}
less_tail->next = greater_head->next;
greater_tail->next = NULL;
ListNode* head = less_head->next;
free(less_head);
free(greater_head);
return head;
}
};七、链表的回文结构
牛客网链接: 链表的回文结构_牛客题霸_牛客网
class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head){
struct ListNode* slow = head,*fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* cur = head;
struct ListNode* newhead = NULL;
while(cur != NULL){
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}
bool chkPalindrome(ListNode* A) {
struct ListNode* mid = middleNode(A);
struct ListNode* newhead = reverseList(mid);
while(A && newhead){
if(A->val != newhead->val){
return false;
}
A = A->next;
newhead = newhead->next;
}
return true;
}
};八、相交链表
LeetCode链接: 160. 相交链表 - 力扣（LeetCode）
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int lenth_A = 0,lenth_B = 0;
struct ListNode* current_A = headA;
struct ListNode* current_B = headB;
while(current_A->next != NULL){
++lenth_A;
current_A = current_A->next;
}
while(current_B->next != NULL){
++lenth_B;
current_B = current_B->next;
}
if(current_A != current_B) return NULL;//尾结点不同，肯定不为相交链表
current_A = headA;
current_B = headB;
if(lenth_A > lenth_B){
for(int i = 0;i < lenth_A - lenth_B; ++i){
current_A = current_A->next;
}
}
else{//lenth_A <= lenth_B
for(int i = 0;i < lenth_B - lenth_A; ++i){
current_B = current_B->next;
}
}
while(current_A != current_B){//此时肯定为相交链表
current_A = current_A->next;
current_B = current_B->next;
}
return current_A;
}
九、复制带随机指针的链表
LeetCode链接: 138. 复制带随机指针的链表 - 力扣（LeetCode）
struct Node* copyRandomList(struct Node* head) {
struct Node* cur = head;
//1.将原链表结点全部拷贝，并将拷贝结点插入原链表其对应的结点的后一个位置
while(cur != NULL){
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
copy->val = cur->val;
copy->next = cur->next;
cur->next = copy;
cur = copy->next;
}
/*
2.
(1)copy结点random指针 指向 其对应结点的random指针指向的结点的后一个
(2)若对应结点的random指针指向NULL,copy结点的random指针也指向NULL
*/
cur = head;
while(cur != NULL){
struct Node* copy = cur->next;
if(cur->random == NULL) copy->random = NULL;
else copy->random = cur->random->next;
cur = copy->next;
}
//3.将插入原链表的所有copy结点，全部解除下来并逐个尾插为一个新的链表，将原链表还原
cur = head;
struct Node* newhead = NULL,*newtail = NULL;
while(cur != NULL){
struct Node* copy = cur->next;
struct Node* next = copy->next;
if(newtail == NULL)
{
newhead = newtail = copy;
}
else
{
newtail->next = copy;
newtail = newtail->next;
}
cur->next = next;
cur = next;
}
//4.返回新链表
return newhead;
}十、链表的带环问题
问题1:
给定一个链表，如何判断链表中是否有环呢？141. 环形链表 - 力扣（LeetCode）
思路: 使用快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，若链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾
bool hasCycle(struct ListNode *head) {
if(head == NULL) return false;
struct ListNode *slow = head,*fast = head;
while(fast !=NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(slow == fast) return true;
}
return false;
}
问题2:
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
142. 环形链表 II - 力扣（LeetCode）
方法一:
在做这道题之前我们必须了解一个定理:
让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。但是为什么呢？
接下来，理论上已经解决，用代码将其实现即可。
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* fast = head,*slow = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
struct ListNode* meet = fast;
while(meet != head){
meet = meet->next;
head = head->next;
}
return meet;
}
}
return NULL;
}方法二:
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* newhead = NULL;
struct ListNode* fast = head,*slow = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
newhead = fast->next;
fast->next = NULL;
}
}
if(newhead == NULL) return NULL;
int length1 = 0,length2 = 0;
struct ListNode* cur = head;
while(cur->next != NULL){
++length1;
cur = cur->next;
}
cur = newhead;
while(cur->next != NULL){
++length2;
cur = cur->next;
}
if(length1 > length2){
for(int i = 0;i < length1 - length2; ++i){
head = head->next;
}
}
if(length1 < length2){
for(int i = 0;i < length2 - length1; ++i){
newhead = newhead->next;
}
}
while(head != newhead){
head = head->next;
newhead = newhead->next;
}
if(head == newhead) return head;
return NULL;
}扩展问题1:
为什么快指针每次走两步，慢指针走一步可以？
若链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度 - 1。
此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇
扩展问题2:
快指针一次走3步，走4步，...n步行吗？ 不行
十一、顺序表和链表的区别
1.存储空间:
顺序表存储空间连续。支持随机访问O(1)
链表的逻辑结构上连续，但物理结构上不一定连续。不支持随机访问O(n) (使用二分查找等算法时，时间复杂度过大)
2.插入与删除操作:
顺序表可能需要移动元素，时间复杂度为O(n)。插入时可能需要扩容，可能存在空间浪费(有一定性能消耗)
链表只需改动指针指向即可。无容量概念，不会浪费空间
3.应用场景:
顺序表适用于元素高效存储、频繁访问
链表适用于任意位置插入删除和删除频繁
4.缓存利用率:
顺序表CPU高速缓存命中率高
链表CPU高速缓存命中率低
CPU缓存命中率
主存、高速缓存和寄存器(带电存储)
磁盘、远程二级存储(不带电存储)
CPU缓存离CPU核心更近，由于电子信号传输是需要时间的，所以离CPU核心越近，缓存的读写速度就越快。但 CPU 的空间很狭小，离 CPU 越近缓存大小受到的限制也越大。所以，综合硬件布局、性能等因素，CPU缓存通常分为大小不等的三级缓存：L1，L2，L3。级别越小越接近 CPU，所以速度也更快，同时也代表着容量越小。
L1 是最接近CPU的, 它容量最小（例如：32K），速度最快，L1缓存每个核上其实有两个L1缓存, 一个用于存数据的 L1d Cache（Data Cache），一个用于存指令的 L1i Cache（Instruction Cache）。
L2缓存更大一些（例如：256K），速度要慢一些, 一般情况下每个核上都有一个独立的L2缓存;
L3缓存是三级缓存中最大的一级，同时也是最慢的一级, 在同一个 CPU 插槽之间的核共享一个 L3 缓存
数据从内存向上，L3->L2->L1,最后到寄存器进行CPU计算。CPU在缓存中找到有用的数据被称为命中率，当缓存中没有CPU所需的数据时(这时称为未命中）CPU才访问内存将数据加载到缓存。CPU并不会一个字节一个字节的加载，效率太低。而是一块一块加载，对于这样的一块一块的数据单位，术语叫“Cache Line”。目前主流的cache line是64字节，也有32和128的。
一般访问某个数据时，先查看其地址是否在缓存中，在就访问，不在则需加载后访问。(一般来说第一次访问都不命中)
缓存命中率 = 从缓存中读取的次数 / 总读取次数
顺序表的存储是一块连续的内存，CPU一块一块地进行数据加载，当访问arr[0]时，arr[1]大概率已经加载到CPU中，减少了加载的时间。
链表空间不连续，每次访问下一个结点大概率需要重新加载。
所以链表缓存命中率低于顺序表，访问速度也低于顺序表