如何将顺序表和链表经典题题解巧妙融合为一个长尾词？

本文共计4950个文字，预计阅读时间需要20分钟。

目录一. 经典面试题

1.移除元素

2.删除有序数组中的重复项

3.合并两个有序数组

二. 链表经典面试题

1.移除链表元素

2.反转一个单链表

3.链表的中间节点

4.链表中倒数第K个节点

目录

一.顺序表经典面试题

1.移除元素

2.删除有序数组中的重复项

3.合并两个有序数组

二.链表经典面试题

1.移除链表元素

2.反转一个单链表

3.链表的中间节点

4.链表中倒数第K个节点

5.合并两个有序链表

6.链表分割

7.链表的回文结构

8.相交链表

9.环形链表

10.环形链表||

---

一.顺序表经典面试题

1.移除元素

oj链接力扣

题目描述:

思路：如果可以开辟额外的数组空间的话，那么我们可以将不是val值的元素依次赋值给新数组即可，但是题目要求不能使用额外的数组空间，我们只能将不是val值的元素赋值给原数组，将之前的值覆盖即可

代码：

int removeElement(int* nums, int numsSize, int val){ int arr[101]; int i=0;//循环变量，以遍历数组 int dst=0;//当前原数组被覆盖的值的数量 for(i=0;i<numsSize;i++) { if(nums[i]!=val)//判断是否数值等于val { nums[dst]=nums[i];//将不相等的元素赋值给原数组 dst++; } } return dst; }

2.删除有序数组中的重复项

OJ链接力扣

题目描述：

思路：我们可以创建一个查找函数，参数是数组和数组大小以及相应的值，对原数组遍历时，调用查找函数判断当前元素是否在前面出现过，如果出现过则跳过该元素，如果没有出现过则赋值给原数组

代码；

int Seach(int* nums, int numsSize,int x)//查找函数 { int i=0; for(i=0;i<numsSize;i++) { if(nums[i]==x) return i;//出现过则返回该元素在数组中下标 } return -1;//没有出现过则返回-1 } int removeDuplicates(int* nums, int numsSize){ int i=0; int dst=1; for(i=1;i<numsSize;i++) { int ret=Seach(nums,i,nums[i]);//调用查找函数判断是否是重复元素 if(ret==-1)//返回-1说明不是重复元素 { nums[dst]=nums[i];赋值给原数组 dst++; } } return dst; }

3.合并两个有序数组

OJ链接力扣

题目描述：

思路：这题可以充分利用双指针的思想，一个指针指向数组1，另一个指针指向数组2，由于此题将数组1的空间设置为两个数组元素数量和的大小，因此最好不要开辟额外的数组空间，两个指针从两个数组末尾开始遍历，将两个数组的元素相比较，比较大的元素则从数组最后一个位置往前赋值，等某个数组遍历完之后，判断数组2的指针是否大于等于0，是的话说明是数组1遍历结束，将数组2剩下的元素依次赋值给原数组。如果是数组1没有遍历完，则不用动它，因为这些元素本身就在数组1前面的位置有序排列

代码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ int ret1=m-1;//数组1的下标，从末尾开始遍历 int ret2=n-1;//数组2的下标，从末尾开始遍历 int j=m+n-1;//总空间的下标，从末尾开始 while(ret1>=0&&ret2>=0)//一个数组遍历完则结束 { if(nums1[ret1]>nums2[ret2])//比较大的元素从总空间最后面依次赋值 { nums1[j]=nums1[ret1]; ret1--; j--; } else if(nums1[ret1]==nums2[ret2]) { nums1[j]=nums2[ret2]; ret2--; j--; } else { nums1[j]=nums2[ret2]; ret2--; j--; } } while(ret2>=0)//数组2没有遍历完，将剩余的元素赋值给总空间 { nums1[j]=nums2[ret2]; ret2--; j--; } }

二.链表经典面试题

1.移除链表元素

oj链接力扣

题目描述：

思路：构建一个带头结点的空的新单链表，以方便尾插，新建一个cur指针依次遍历原链表，判断各个节点的值是否为要删除的值，如果不是，则将该节点尾插到新链表，指针往后走，如果是，定义一个next指针指向下一个节点，将当前节点删除，然后cur指针等于next，即指针继续往后走，直到遍历指针cur指针为空遍历则结束，最后将新链表的头节点删除，头指针指向第一个节点，最后返回新链表的头指针即可

代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* cur=head;//定义遍历指针 struct ListNode* guard,*tail;//定义带头节点的新链表 guard=tail=(struct ListNode*)malloc(sizeof(struct ListNode));//开辟头结点 while(cur) { if(cur->val!=val)//如果不是要删除的值，则尾插到新链表 { tail->next=cur; tail=tail->next; cur=cur->next; } else//是则删除 { struct ListNode *next=cur->next; free(cur); cur=next; } } tail->next=NULL;//将尾及诶点的next置空 struct ListNode *newnode=guard->next;//将头指针指向第一个节点 free(guard);//删除头结点 return newnode; }

2.反转一个单链表

OJ链接力扣

题目描述：

思路：首先判断原链表是否为空，为空则返回空，不为空则定义两个遍历指针遍历原链表，再定义一个空的新链表，依次遍历原链表的每一个节点，然后将每个节点头插到新链表，即形成反转效果，最后将新链表的头指针返回即可

代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head){ struct ListNode* newnode=NULL;//新建一个空链表 struct ListNode* cur=head;//新建两个遍历指针 struct ListNode* next=head; if(cur==NULL)//原链表为空则返回空 return head; else { while(cur)//遍历原链表的节点，将每个节点头插到新链表 { next=next->next; cur->next=newnode; newnode=cur; cur=next; } } return newnode; }

3.链表的中间节点

OJ链接力扣

题目描述：

思路1：首先判断原链表是否为空，为空则返回空，定义一个遍历指针遍历原链表，统计出原链表节点的数量num，然后再让遍历指针从头开始走num/2（无论原链表节点数量为奇数还是偶数都可）个节点，将此节点返回即可

思路2：首先判断原链表是否为空，为空则返回空，定义两个快慢指针low和fast，两个指针都从头开始走，慢指针一次走一步，快指针一次走两步，快指针走的路程是慢指针的2倍，当快指针走到链表末尾时，慢指针刚好走到链表中间，此时返回慢指针指向的节点即可

代码：

思路1： struct ListNode* middleNode(struct ListNode* head){ struct ListNode* cur=head;//定义一个遍历指针 int num=0;//用来统计链表节点的数量 while(cur)//遍历统计数量 { num++; cur=cur->next; } cur=head; int i=0; for(i=0;i<num/2;i++)//让指针走到中间节点 { cur=cur->next; } return cur; } 思路2： struct ListNode* middleNode(struct ListNode* head){ struct ListNode*low=head;//定义快慢指针 struct ListNode*fast=head; if(head==NULL)//原链表为空则返回空 return NULL; while(fast&&fast->next)//节点数量为奇数和偶数的两种结束条件 { low=low->next;//慢指针一次走一步 fast=fast->next->next;//快指针一次走两步 } return low; }

4.链表中倒数第K个节点

OJ链接链表中倒数第k个结点_牛客题霸_牛客网

题目描述：

思路1：首先判断链表是否为空，为空则返回空，定义一个遍历指针统计链表中节点的数量，当k小于等于或者大于节点的数量时返回空，然后让遍历指针从头开始走n-k步，此时指向的便是倒数第K个节点，返回即可

思路2：首先判断链表是否为空，为空则返回空，定义一个遍历指针统计链表中节点的数量，当k小于等于或者大于节点的数量时返回空，定义两个指针p1和p2都指向头结点，两个节点每次都只走一步，让p1指针先走K-1步，之后两个指针一起走，当p1指针走到最后一个节点时，p2此时刚好指向倒数第K个节点，返回p2即可

代码：

思路1： struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { int i=0; struct ListNode*cur=pListHead;//遍历指针统计节点数量 int n=0; while(cur) { n++; cur=cur->next; } cur=pListHead; if(k>0&&k<=n)//判断K的合法性，合法则让遍历指针走n-k步 { for(i=0;i<n-k;i++)//让遍历指针走n-k步 { cur=cur->next; } return cur; } else//不合法返回空 { return NULL; } } 思路2： struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { if(pListHead==NULL)//判断链表是否为空，为空则返回为空 return NULL; struct ListNode*cur=pListHead;//定义三个遍历指针 struct ListNode*p1=pListHead; struct ListNode*p2=pListHead; int num=0;//记录节点数量 while(cur)//遍历统计节点数量 { num++; cur=cur->next; } if(k<=0||k>num)//判断k的合法性 return NULL; k=k-1; while(k--)//让p1先走k-1步 { p1=p1->next; } while(p1->next)//之后两个指针一起走 { p1=p1->next; p2=p2->next; } return p2; }

5.合并两个有序链表

OJ链接力扣

题目描述：

思路：定义一个带头结点的新链表，定义两个指针分别指向两个链表，将两个链表的节点的值进行比较，较小的值则尾插到新链表中，然后指向该值地指针继续往后走，较大的值地指针则不动，当某个链表遍历结束后则结束比较，然后检查哪个链表没有遍历完，没有遍历完的元素一定是比较大的元素，直接尾插到新链表中即可，最后将新链表的头指针指向第一个节点，删除头结点返回头指针即可

代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode *cur1=list1;//两个指针分别指向两个链表 struct ListNode *cur2=list2; struct ListNode *guard,*tail;//新建一个带头结点的单链表 guard=tail=(struct ListNode*)malloc(sizeof(struct ListNode));//开辟头结点 while(cur1&&cur2)//遍历两个链表，当有一个链表遍历完则结束 { if(cur1->val<cur2->val)//节点的值比较，较小的值尾插到新链表 { tail->next=cur1; tail=tail->next; cur1=cur1->next; } else { tail->next=cur2; tail=tail->next; cur2=cur2->next; } } //检查哪个链表没有遍历完，没有遍历完的链表的节点则尾插到新链表中 if(cur1==NULL) { while(cur2) { tail->next=cur2; tail=tail->next; cur2=cur2->next; } tail->next=NULL; } else if(cur2==NULL) { while(cur1) { tail->next=cur1; tail=tail->next; cur1=cur1->next; } tail->next=NULL; } else{ return NULL; } struct ListNode*newnode=guard->next;//头指针指向第一个节点 free(guard);//删除头结点 return newnode; }

6.链表分割

OJ链接链表分割_牛客题霸_牛客网

题目描述：

思路：先判断原链表是否为空，为空则返回空，定义一个遍历指针遍历原链表，定义两个带头结点的空链表，将原链表值小于x的节点尾插到一个新链表中，将值大于x的节点尾插到新一个新链表中，将两个新链表的头节点删除，头指针指向第一个节点，然后将两个新链表链接在一起即可，最后返回链接后链表的头指针

代码：

ListNode* partition(ListNode* pHead, int x) { // write code here if(pHead==NULL)//判断原链表是否为空 return NULL; ListNode* cur=pHead;//定义遍历指针 ListNode* guard1,*tail1,*guard2,*tail2;//定义两个新链表 //开辟头结点 guard1=tail1=(ListNode*)malloc(sizeof(ListNode)); guard1->next=NULL; guard2=tail2=(ListNode*)malloc(sizeof(ListNode)); guard2->next=NULL; //遍历原链表，值小于x的节点尾插到一个新链表中，大于x的节点尾插到另一个新链表中 while(cur) { if(cur->val<x) { tail1->next=cur; tail1=tail1->next; cur=cur->next; } else { tail2->next=cur; tail2=tail2->next; cur=cur->next; } } tail1->next=guard2->next;//两个新链表链接在一起 tail2->next=NULL;//链表的最后一个节点next置空 ListNode* newnode1=guard1->next;//头指针指向第一个节点 ListNode* newnode2=guard2->next; //删除头结点 free(guard1); free(guard2); return newnode1; } }

7.链表的回文结构

OJ链接链表的回文结构_牛客题霸_牛客网

题目描述：

思路：这道题是前面几道题的综合，先判断原链表是否为空，为空则返回，调用第3题的函数找到原链表的中间链表，然后再调用第2题的函数将原链表后半部分反转，然后原链表和后部分反转链表遍历每个节点相比较，如果有节点不相等则返回false，相等则继续往下遍历，直到遍历结束然后返回true

代码：

//返回中间节点 struct ListNode* middleNode(struct ListNode* head){ struct ListNode* cur=head; int num=0; while(cur) { num++; cur=cur->next; } cur=head; int i=0; for(i=0;i<num/2;i++) { cur=cur->next; } return cur; } //反转链表 struct ListNode* reverseList(struct ListNode* head){ struct ListNode* newnode=NULL; struct ListNode* cur=head; struct ListNode* next=head; if(cur==NULL) return head; else { while(cur) { next=next->next; cur->next=newnode; newnode=cur; cur=next; } } return newnode; } bool chkPalindrome(ListNode* A) { // write code here ListNode *mid=middleNode(A);//返回原链表的中间节点 ListNode *rhead=reverseList(mid);//翻转原链表的后半部分 while(A&&rhead)//遍历两个链表，比较节点的值 { if(A->val!=rhead->val) return false; A=A->next; rhead=rhead->next; } return true; } }

8.相交链表

OJ链接力扣

题目描述：

思路：定义两个遍历指针，依次遍历两个链表统计出两个链表节点的个数，计算出两个链表节点数量的差值，让节点数量多的链表遍历走差值的步数，然后两个链表一起遍历，如果两个指针指向的节点相同，则该节点则为相交节点返回该节点，否则两个指针继续往后遍历直到遍历结束，遍历结束依然没有找到相交节点则返回空

代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { //定义两个遍历指针 struct ListNode *cur1=headA; struct ListNode *cur2=headB; //分别统计两个链表节点数量 int num1=0; int num2=0; //遍历统计两个链表节点数量 while(cur1) { num1++; cur1=cur1->next; } while(cur2) { num2++; cur2=cur2->next; } cur1=headA; cur2=headB; //让节点数量多的链表遍历指针先走差值的步数 if(num1>num2) { int k=num1-num2; while(k--) cur1=cur1->next; } else if(num1<num2) { int k=num2-num1; while(k--) cur2=cur2->next; } //两个链表一起遍历 while(cur1) { //两个链表的节点相比较，相同则返回 if(cur1==cur2) return cur1; if(cur1->next==cur2->next) return cur1->next; //不同则继续遍历 else { cur1=cur1->next; cur2=cur2->next; } } return NULL; }

9.环形链表

OJ链接力扣

题目描述：

思路：这道题可以充分利用快慢指针的思想，定义一个慢指针low和快指针fast，分别一次走一步和两步，链表分为环区和直线区，当fast指针走到直线区末尾即环区入口时，low指针刚好走到直线区的中间，当慢指针入环时，快指针已经在环区走了若干圈，当两个指针一起走时，每走一次两个指针的距离便减小1，若干次后两个指针必会相遇，则证明该链表是环形链表，如果追不上或者指针指向空则证明该链表不是环形链表

代码：

bool hasCycle(struct ListNode *head) { if(head==NULL)//判断原链表是否为空，为空则返回空 return false; //定义两个快慢指针 struct ListNode* low=head; struct ListNode* fast=head; low=low->next;//慢指针每次走一步 fast=fast->next->next;//快指针每次走两步 while(low!=fast&&fast!=NULL)//两个指针一直走，直到相遇或者为空结束 { low=low->next; fast=fast->next->next; } if(low==fast)//相遇则返回真 return true; if(fast==NULL)//为空则返回假 return false; }

10.环形链表||

oj链接力扣

题目描述：

思路（结论）：先判断链表是否为空或者只有一个节点，是则返回NULL,在第9题快慢指针相遇的基础上，我们让一个指针从头开始走，另一个指针从相遇点开始走，每个指针每次走一步，两个指针相遇的地方便是入环的第一个节点

证明：假设直线区长度为L，环的长度为C，快慢指针相遇点至入环口的距离为N，第9题的快指针走的路程是慢指针的两倍

慢指针走的路程：L+N

快指针走的路程：假设快指针已经在环走了K圈，则路程为L+KC+N

则由（L+N）*2=L+KC+N，化解得L=KC-N=(K-1)C+C-N,(K-1)C可以认为指针走了K圈又回到原点，故得证L=C-N

代码：

struct ListNode *detectCycle(struct ListNode *head) { if(head==NULL||head->next==NULL)//判断链表是否为空或者只有一个节点 return NULL; //定义两个快慢指针 struct ListNode *low=head; struct ListNode *fast=head; while(fast&&fast->next)//快慢指针遍历 { low=low->next; fast=fast->next->next; //如果快慢指针相遇则让一个指针从头开始走，另一个指针从相遇点开始走 if(low==fast) { struct ListNode *meet=low; while(head!=meet) { head=head->next; meet=meet->next; } return meet; } } //上面的循环结束到这里说明链表没有环，返回空 return NULL; }

好啦，顺序表和链表经典面试题就先学习到这里，如果文章对您有帮助，欢迎一键三连~

最后附上寄语：种一棵树最好的时间是十年前，其次是现在