目录
一.顺序表经典面试题
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;
}好啦，顺序表和链表经典面试题就先学习到这里，如果文章对您有帮助，欢迎一键三连~
最后附上寄语：种一棵树最好的时间是十年前，其次是现在