顺序表和链表经典面试题

墨蓝 2023-10-08 22:51 24阅读 0赞

**目录**

一.顺序表经典面试题

1.移除元素

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

3.合并两个有序数组

二.链表经典面试题

1.移除链表元素

2.反转一个单链表

3.链表的中间节点

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

5.合并两个有序链表

6.链表分割

7.链表的回文结构

8.相交链表

9.环形链表

10.环形链表||

--------------------

## 一.顺序表经典面试题 ##

### 1.移除元素 ###

oj链接[力扣][Link 1]

题目描述:

![61a055023f4140fba28fce825819731a.png][]

> 思路：如果可以开辟额外的数组空间 的话，那么我们可以将不是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链接[力扣][Link 2]

题目描述：![800f7026f72a43ff86a2fe98214c612a.png][]

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

代码；

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链接[力扣][Link 3]

题目描述：

![88f370749b134f75aba44264db640b83.png][]

> 思路：这题可以充分利用双指针的思想，一个指针指向数组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链接[力扣][Link 4]

题目描述：

![78ef525654bb4e178f2107bfea9da84b.png][]

> 思路：构建一个带头结点的空的新单链表，以方便尾插，新建一个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链接[力扣][Link 5]

题目描述：

![229d66fccbf34f59964be026de25efe7.png][]

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

代码：

/**
     * 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链接[力扣][Link 6]

题目描述：

![74971b9d48dc4786b13df2c38579232e.png][]

> 思路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个结点\_牛客题霸\_牛客网][k]

题目描述：

![19384021c822486483ecfa90aefa7d1a.png][]

> 思路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链接[力扣][Link 7]

题目描述：

![0803d8f854c04f04be0c67eca4ecf082.png][]

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

代码：

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链接[链表分割\_牛客题霸\_牛客网][Link 8]

题目描述：

![262c64828c8846bf8b5ece520f0ddc84.png][]

> 思路：先判断原链表是否为空，为空则返回空，定义一个遍历指针遍历原链表，定义两个带头结点的空链表，将原链表值小于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链接[链表的回文结构\_牛客题霸\_牛客网][Link 9]

题目描述：

![94296c6c285348cd85e7e8e1fcac8bde.png][]

> 思路：这道题是前面几道题的综合，先判断原链表是否为空，为空则返回，调用第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链接[力扣][Link 10]

题目描述：

![68902d91c6ae41d4bb11adadef987c07.png][]

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

代码：

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链接[力扣][Link 11]

题目描述：

![1fa96ba0ad16450598d6f09d9d69e835.png][]

> 思路：这道题可以充分利用快慢指针的思想，定义一个慢指针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链接[力扣][Link 12]

题目描述：

![3b5de89c748f43ad8c7c6dac5405c0e4.png][]

> 思路（结论）：先判断链表是否为空或者只有一个节点，是则返回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

![0e70a2d4c25f4e06a9409bdec671cd63.png][]

代码：

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

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

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

[Link 1]: https://leetcode.cn/problems/remove-element/
[61a055023f4140fba28fce825819731a.png]: https://img-blog.csdnimg.cn/61a055023f4140fba28fce825819731a.png
[Link 2]: https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
[800f7026f72a43ff86a2fe98214c612a.png]: https://img-blog.csdnimg.cn/800f7026f72a43ff86a2fe98214c612a.png
[Link 3]: https://leetcode.cn/problems/merge-sorted-array/
[88f370749b134f75aba44264db640b83.png]: https://img-blog.csdnimg.cn/88f370749b134f75aba44264db640b83.png
[Link 4]: https://leetcode.cn/problems/remove-linked-list-elements/description/
[78ef525654bb4e178f2107bfea9da84b.png]: https://img-blog.csdnimg.cn/78ef525654bb4e178f2107bfea9da84b.png
[Link 5]: https://leetcode.cn/problems/reverse-linked-list/description/
[229d66fccbf34f59964be026de25efe7.png]: https://img-blog.csdnimg.cn/229d66fccbf34f59964be026de25efe7.png
[Link 6]: https://leetcode.cn/problems/middle-of-the-linked-list/description/
[74971b9d48dc4786b13df2c38579232e.png]: https://img-blog.csdnimg.cn/74971b9d48dc4786b13df2c38579232e.png
[k]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[19384021c822486483ecfa90aefa7d1a.png]: https://img-blog.csdnimg.cn/19384021c822486483ecfa90aefa7d1a.png
[Link 7]: https://leetcode.cn/problems/merge-two-sorted-lists/description/
[0803d8f854c04f04be0c67eca4ecf082.png]: https://img-blog.csdnimg.cn/0803d8f854c04f04be0c67eca4ecf082.png
[Link 8]: https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
[262c64828c8846bf8b5ece520f0ddc84.png]: https://img-blog.csdnimg.cn/262c64828c8846bf8b5ece520f0ddc84.png
[Link 9]: https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
[94296c6c285348cd85e7e8e1fcac8bde.png]: https://img-blog.csdnimg.cn/94296c6c285348cd85e7e8e1fcac8bde.png
[Link 10]: https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
[68902d91c6ae41d4bb11adadef987c07.png]: https://img-blog.csdnimg.cn/68902d91c6ae41d4bb11adadef987c07.png
[Link 11]: https://leetcode.cn/problems/linked-list-cycle/description/
[1fa96ba0ad16450598d6f09d9d69e835.png]: https://img-blog.csdnimg.cn/1fa96ba0ad16450598d6f09d9d69e835.png
[Link 12]: https://leetcode.cn/problems/linked-list-cycle-ii/description/
[3b5de89c748f43ad8c7c6dac5405c0e4.png]: https://img-blog.csdnimg.cn/3b5de89c748f43ad8c7c6dac5405c0e4.png
[0e70a2d4c25f4e06a9409bdec671cd63.png]: https://img-blog.csdnimg.cn/0e70a2d4c25f4e06a9409bdec671cd63.png