顺序表和链表经典面试题

时间：2020-12-23 01:13:41

目录

一.顺序表经典面试题

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;
}

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

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

标签：

相关文章