【leetcode合集】如何知道自己是否掌握了数组与链表？试试这几道题目吧！-Toy模板网

这篇具有很好参考价值的文章主要介绍了【leetcode合集】如何知道自己是否掌握了数组与链表？试试这几道题目吧！。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【leetcode合集】如何知道自己是否掌握了数组与链表？试试这几道题目吧！,刷题训练营,leetcode,链表,算法,顺序表,c语言

1.数组题目合集

1.1 leetcode.27 移除元素

1.2 leetcode.26 删除有序数组中的重复项

1.3 leetcode.88 合并两个有数数组

2.链表题目合集

2.1 leetcode.203 移除链表元素

2.2 leetcode.206 反转链表

2.3 leetcode.876 链表的中间结点

2.4 牛客链表中倒数第k个结点

2.5 leetcode.21 合并两个有序链表

2.6 leetcode.相交链表

2.7 leetcode.141 环形链表

2.8 leetcode.142 环形链表Ⅱ

2.9 复制带随机指针的链表

1.数组题目合集

1.1 leetcode.27 移除元素

OJ链接：移除元素（点此可跳转）

解题思路：题目要求不能开辟新的数组，所以只能在原数组上进行操作。我的做法是，遇到值等于val的元素时，将其与数组末尾的元素互换位置，再令数组的长度-1就达到了删除元素的效果。

解题实战：文章来源地址https://www.toymoban.com/news/detail-824379.html

int removeElement(int* nums, int numsSize, int val){
    int i=0;
    int j=0;
    while(i<numsSize)
    {
        while(val==nums[i]&&i<numsSize)
        {
           nums[i]=nums[numsSize-1];
           numsSize--;
        }
        i++;
    }
    return numsSize;

}

1.2 leetcode.26 删除有序数组中的重复项

OJ链接：删除有序数组中的重复项

解题思路：本题采用双指针的方式，p1来记录当前位置，p2来寻找与p1处的值不相同的元素。找到后让p2处的值与p1+1处的值进行交换。一直循环本操作，直至p2走完整个数组。

解题实战：

int removeDuplicates(int* nums, int numsSize){
    int* p1=nums;
    int* p2=nums+1;
    int i=0;
    int returnSize=1;//至少有一个元素
    for(i=0;i<numsSize-1;i++)
    {
        if(*p1!=*(p2+i))
        {
            *(++p1)=*(p2+i);
            returnSize++;
        }
    }
    return returnSize;
}

1.3 leetcode.88 合并两个有数数组

OJ链接：合并两个有序数组

解题思路：采用双指针的方式，p1用来遍历nums1数组，p2用来遍历nums2数组。

此时我们需要另外开辟一个新的数组（掌握后也可以不开），p1,p2同时前进，哪一个指针指向的值比较小，哪一个就填充到新数组里，然后该指针向后移动一位，另一个指针不动。

循环此步骤，直至两个数组中某一个数组遍历完成。

之后将未遍历完成的数组剩下的元素全部拷贝到新数组。最后一步，将新数组中的元素拷贝到nums1数组中。

解题实战：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int i=0;
    int j=0;
    int arr[200]={0};
    int* p1=nums1;
    int* p2=nums2;
    int k=0;//记录arr数组里元素的个数
    if(nums2Size==0)
        return;
    while(i<nums1Size-nums2Size&&j<nums2Size)
    {
        if(p1[i]<p2[j])
        {
            arr[k]=p1[i];
            i++;
        }
        else
        {
            arr[k]=p2[j];
            j++;
        }
        k++;
    }
    if(i==nums1Size-nums2Size)
    {
        for(;j<nums2Size;j++)
        {
            arr[k++]=p2[j];
        }
    }
    if(j==nums2Size)
    {
        for(;i<nums1Size-nums2Size;i++)
        {
            arr[k++]=p1[i];
        }
    }
    for(k=0;k<nums1Size;k++)
    {
        nums1[k]=arr[k];
    }
}

2.链表题目合集

2.1 leetcode.203 移除链表元素

OJ链接：移除链表元素

解题思路：本题我采用双指针的方式（双指针并不意味着仅仅只有两个指针）。首先我们需要一个新的头结点 newhead 。newtail 指针用来记录新的链表的尾部，方便插入数据。cur指针用来遍历原链表。cur从原链表的头部开始，每当遇到不等于val的结点时，将该结点尾插到新链表。最后，只需返回newhead即可。

解题实战：

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* newhead=NULL;
    struct ListNode* newtail=NULL;
    struct ListNode* cur=head;


    while(cur)
    {
        if(cur->val!=val)
        {
            //如果是首次尾插，分情况处理
            if(newtail==NULL)
            {
                newhead=newtail=cur;
            }
            //一般情况
            else
            {
                newtail->next=cur;
                newtail=cur;
            }
        }
        //保存cur->next
        struct ListNode* next=cur->next;
        cur->next=NULL;
        cur=next;
    }

    return newhead;
}

2.2 leetcode.206 反转链表

OJ链接：反转链表

解题思路：本题采用带哨兵位的方式。定义一个newhead作为哨兵位的头节点。cur用来遍历原链表。从头到尾将每一个结点都头插到新链表中。解题中所有的操作都是链表的基础操作。

解题实战：

struct ListNode* reverseList(struct ListNode* head){

    struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
    newhead->next=NULL;

    struct ListNode* cur=head;

    while(cur)
    {
        struct ListNode* cur_next=cur->next;
        struct ListNode* newhead_next=newhead->next;

        newhead->next=cur;
        cur->next=newhead_next;

        cur=cur_next;
    }

    return newhead->next;
}

2.3 leetcode.876 链表的中间结点

OJ链接：链表的中间结点

解题思路：定义一个变量count用来记录链表总共的结点数。利用tail指针遍历链表，用count来控制tail的位置，在coont/2的位置处停止遍历并返回tail结点。

解题实战：

struct ListNode* middleNode(struct ListNode* head){
    
    int count=0;
    struct ListNode* tail=head;
    //统计链表长度
    while(tail)
    {
        count++;
        tail=tail->next;
    }
    int mid=count/2+1;
    tail=head;
 
    //寻找中间结点
    while(mid>1)
    {
        tail=tail->next;
        mid--;
    }

    return tail;
}

2.4 牛客链表中倒数第k个结点

OJ链接：链表中倒数第k个结点

解题思路：与上一题思路相同，只需控制遍历链表的深度即可。

解题实战：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {

    int count = 0;
    struct ListNode* tail=pListHead;
    //统计链表的长度
    while(tail)
    {
        count++;
        tail=tail->next;
    }
    //tail从头再来
    tail=pListHead;
    int i=count-k;
    //找倒数第K个结点
    while(i>0)
    {
        tail=tail->next;
        i--;
    }
    //如果k比链表的长度还要大，则返回NULL
    if(k>count)
        return NULL;

    return tail;
}

2.5 leetcode.21 合并两个有序链表

OJ链接：合并两个有序链表

解题思路：与第3题的思路相同，分别用tail1和tail2遍历两个链表。哪个结点的val较小，就把哪一个结点尾插到新链表，直至有一个链表全部遍历完毕。最后把未遍历完毕的链表直接链接到新链表的尾部，并返回newhead->next。

解题实战：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    
    struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
    newhead->next=NULL;
    struct ListNode* tail=newhead;

    
    struct ListNode* tail1=list1;
    struct ListNode* tail2=list2;
    //遍历两个链表
    while(tail1&&tail2)
    {
        //哪一个结点的val较小就将哪个结点尾插到新链表
        if(tail1->val < tail2->val)
        {
            tail->next=tail1;
            tail=tail1;
            tail1=tail1->next;
        }
        else
        {
           
            tail->next=tail2;
            tail=tail2;
            tail2=tail2->next;
        }
    }

    if(tail1==NULL&&tail2==NULL)
    {
        return NULL;
    }

    if(tail1==NULL)
    {
            tail->next=tail2;
    }

    if(tail2==NULL)
    {
        tail->next=tail1;
    }

    return newhead->next;

2.6 leetcode.相交链表

OJ链接：相交链表

解题思路：与判断两个数组中有无相同元素类似。定义两个指针tailA和tailB分别遍历两个链表。采用双层循环的方式，直至找到相同的结点为止。

解题实战：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* tailA=headA;

    while(tailA)
    {
        struct ListNode* tailB=headB;
        while(tailB)
        {
            if(tailA==tailB)
            {
                return tailA;
            }
            tailB=tailB->next;
        }
        tailA=tailA->next;
    }
    return NULL;
}

2.7 leetcode.141 环形链表

OJ链接： 环形链表

解题思路：看到题目时，首先想到的是这与给出一个val，然后在数组中查找是否有与val值相同的元素。所以，这道题我们利用一个数组将链表的结点全部存储起来，然后查找数组中，是否有与链表的尾结点t的next结点相同的结点。因为无法确定何时到达链表的尾结点，所以，本题的精髓在于用一个变量cur来控制链表的尾，依次假设尾结点就是cur。

解题实战：

bool hasCycle(struct ListNode *head) {
    //用来存储结点
    struct ListNode* arr[10000];
    struct ListNode* cur=head;
    int i=0;

    //特殊情况特殊处理
    if(head==NULL||head->next==NULL)
        return false;

    while(cur->next)
    {
        //每经过一个结点，就添加到数组中
        arr[i]=cur;
        i++;
        //此时尾我们假设结点为cur，遍历数组是否有与cur->next相同的元素
        cur=cur->next;
        
        for(int j=0;j<i;j++)
        {
            if(arr[j]==cur->next)
                return true;
        }
    }

    return false;
}

2.8 leetcode.142 环形链表Ⅱ

OJ链接：环形链表 II

解题思路：本题与上一题几乎没有区别，代码也几乎相同。

解题实战：

struct ListNode *detectCycle(struct ListNode *head) {

    //用来存储结点
    struct ListNode* arr[10000];
    struct ListNode* cur=head;
    int i=0;

    //特殊情况特殊处理
    if(head==NULL||head->next==NULL)
        return NULL;

    while(cur->next)
    {
        //每经过一个结点，就添加到数组中
        arr[i]=cur;
        i++;
        //此时尾我们假设结点为cur，遍历数组是否有与cur->next相同的元素
        cur=cur->next;
        
        for(int j=0;j<i;j++)
        {
            if(arr[j]==cur->next)
                return cur->next;
        }
    }

    return NULL;

2.9 复制带随机指针的链表

OJ链接：复制带随机指针的链表

解题思路：我们每复制一个结点，就将复制出的克隆体结点插入到该本体结点的后面。之后，最关键的一步是复制random指针。当我们完成第一步之后，就发现复制random指针变得十分方便。只需使每个克隆体结点的random等于本体结点的random->next。最后，在将这些克隆体结点链接起来即可。

解题实战：

struct Node* copyRandomList(struct Node* head) {

    if(head==NULL)
        return NULL;
    
    struct Node* tail=head;
    //复制每个结点并将复制出的结点插入到原来结点的后面
    while(tail)
    {
        struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
        struct Node* next=tail->next;

        tail->next=newNode;
        newNode->next=next;

        newNode->val=tail->val;
        newNode->random=tail->random;

        tail=next;
    }
    //依次修改每个结点的random指针
    tail=head;
    while(tail)
    {
        if(tail->random!=NULL)
        {
            tail->random=tail->random->next;
        }            
        tail=tail->next;
    }
    //将所有复制出的结点链接起来
    tail=head->next;
    while(tail->next)
    {
        tail->next=tail->next->next;
        tail=tail->next;
    }
    return head->next;
}

到了这里，关于【leetcode合集】如何知道自己是否掌握了数组与链表？试试这几道题目吧！的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！