数组or链表题(力扣or牛客网)

目录

1.数组

一.移除元素

1.1.题目链接：移除元素

1.2.思路分析 

1.3.代码实现 

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

2.1.题目链接：26. 删除有序数组中的重复项

 2.2.思路分析

 2.3.代码实现

三.合并俩个有序数组

3.1.题目链接：合并两个有序数组

 3.2.思路分析

 3.3代码实现

2.链表

一.移除链表元素

1.1题目链接：移除链表元素

 1.2思路分析

 1.3.代码

二.反转链表

2.1题目链接：反转链表

 2.2.思路分析

 2.3.代码

三.链表的中间结点

3.1.题目链表:链表的中间结点

 3.2.思路分析

 3.3.代码

四.链表中倒数第K个结点 

4.1.题目链接：链表中倒数第K个结点

4.2.思路分析 

 4.3.代码

五.合并俩个链表

5.1.题目链接：合并两个有序链表

 5.2.思路分析

 5.3.代码

六.分割链表

6.1.题目链接：链表分割

 6.2.思路分析

 6.3.代码

七.回文链表

7.1.题目链接：回文链表

​编辑 7.2.思路分析

7.3.代码实现

八.相交链表

8.1.题目链接：相交链表

8.2.思路分析 

8.3.代码实现

九.环形链表

9.1.题目链接：环形链表

 9.2.思路分析

9.3.代码实现

十.环形链表2

10.1.题目链接：环形链表2

 10.2.思路分析

 10.3.代码实现

---

1.数组

一.移除元素

1.1.题目链接：移除元素

 

1.2.思路分析 

 思路：（快慢指针）

fast=0；slow=0开始

<1>等于val：fast++

<2>不等于val：赋值(fast位置对应的值赋值到slow位置对应的值)；slow++；fast++

直到fast=numsSize结束

前俩步都是slow++,和fast++，slow到2，fast到2，遇到等于val的时候，只用fast++

1.fast从遇到第一个2开始，直到遇到不等于val时，3先赋值给slow所在的位置

 2.然后slow++,fast++,然后继续再次遇到不等于val的时候，0赋值给slow所在位置，然后slow/fast++即可

 3.直到fast=numsSize,最终结果【0，1，3，0，4】长度为5

1.3.代码实现 

int removeElement(int* nums, int numsSize, int val)
{
    int slow=0;
    int fast=0;
    while(fast<numsSize)
    {
        if(nums[fast]!=val)
        {
                nums[slow]=nums[fast];
                slow++;
        }
         fast++;
    }
    return slow;
}

如果这题会了，那么就自己思考做一下下面的变式题吧，也是利用快慢指针来解决，如果思路不明，可以看我的思路解析，即可解决问题。 

---

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

2.1.题目链接：26. 删除有序数组中的重复项

 

 2.2.思路分析

思路：(快慢指针）

fast=1；slow=0开始

<1>俩者相等：fast++

<2>俩者不等：slow++；赋值(fast位置对应的值赋值到slow位置对应的值)；fast++

直到fast=numsSize结束

1.初始状态，slow=0，fast=1 

 2.当fast所对应的值不等于上面一个图中slow对应的值时，slow先++

 3.然后将fast对应的值1赋值给slow对应的值，然后fast++

 4.一直fast++，遇到与上图slow对应的1不相等的时候，slow++，跳到下图的位置

 5.然后fast++，继续进行对比是否相等

 6.然后fast走到等于numsSize时，就可以返回slow+1结束。

 2.3.代码实现

int removeDuplicates(int* nums, int numsSize)
{
    int slow=0;
    int fast=1;
   while(fast<numsSize)
   {
       if(nums[slow]!=nums[fast])
        {
            slow++;
            nums[slow]=nums[fast];
        }
        fast++;
   }
    return slow+1;
}

---

三.合并俩个有序数组

3.1.题目链接：合并两个有序数组

 3.2.思路分析

思路：(双指针）利用双指针问题

将俩个数组从头开始，遇到数值小的赋值到新开辟的数组中去，然后那个数组下标往后移一位，然后继续比较，直到等于数组长度位置就结束循环，如果俩个数组长度不一或者一个赋值完一个未赋值完，最后那么就得判断一i下，将未赋值完的数组后面的元素全部都赋值到开辟数组中去(原俩个数组都是有序的，不用进行比较排序），然后就用memcpy拷贝到nums1数组中去，因为返回是返回nums1数组中。（如果遇到相等，我都是和小于一样看待)

特殊情况：1.nums1中无元素，就用memcpy将nums2元素拷贝到nums1中

                  2.nums2中无元素，就直接返回nums1

                  3.最后记住判断一下是否都拷贝完成，用if判断是否(i<m)或者(j<n)

                     因为有些数组赋值完，另一个数组未赋值完，就得判断一下。

1. nums1数组中1小于2，2等于2，都弄到新数组中去，然后i++

 2.遇到nums2数组元素大于nums1数组元素，就将nums2数组元素赋值到新数组中去，然后j++

 3.nums1数组中元素全部都已经赋值到新数组中去了

4.nums1剩下的元素就全部放进新数组中去即可 

 

 3.3代码实现

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    if(n==0)
    {
        return nums1;
    }
    if(m==0)
    {
        memcpy(nums1,nums2,sizeof(int)*n);
        return nums1;
    }
    int *a=(int*)malloc(sizeof(int)*(nums1Size));
    int i=0;
    int j=0;
    int k=0;
    while(i<m&&j<n)
    {
        if(nums1[i]<=nums2[j])
        {
            a[k]=nums1[i];
             k++;
            i++;
        }
        else
        {
            a[k]=nums2[j];
            j++;
            k++;
        }
    }
    if(i<m)
    {
        while(i<m)
        {
            a[k]=nums1[i];
            i++;
            k++;
        }
    }
    if(j<n)
    {
        while(j<n)
        {
            a[k]=nums2[j];
            j++;
            k++;
        }
    }
    memcpy(nums1,a,sizeof(int)*(nums1Size));
    return nums1;
}

相信以上数组的基础上，我们接下来看看链表有关的题目吧~

如果对链表知识有所不清楚，请点击链表一万字详细解说 

---

---

---

2.链表

一.移除链表元素

1.1题目链接：移除链表元素

 1.2思路分析

构建一个新的链表，如果找到不同的就插入进新的链表

注意：头结点的删除

 这是用以上思路写出的代码

运行结果出错，所以我们就得考虑，为什么错误了？

如果头结点就是所要移除的值，prev=NULL，那还能用将cur->next指向prev->next吗？

显然是不可以的 

所以将head来解决

 1.3.代码

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode*prev=NULL;
    struct ListNode*cur=head;
    while(cur)
    {
        if(cur->val!=val)
        {
            prev=cur;
            cur=cur->next;
        }
        else
        {
            if(cur==head)
            {
                head=head->next;
                free(cur);
                cur=head;
            }
            else
            {
                 prev->next=cur->next;
                free(cur);
                cur=prev->next;
            }
        }
    }
    return head;
}

---

二.反转链表

2.1题目链接：反转链表

 2.2.思路分析

思路：三指针

1.先迭代   n2->next=n1

2.赋值   n1=n2,n2=n3,n3=n3->next

循环往复，对于n个元素依次将其链表的方向改变，有三个量： n3用于记录当前操作项的下一项

 2.3.代码

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode*n1=NULL;//新链表的第一个结点，头结点
    struct ListNode*n2=head;//保存旧链表
    while(n2)
    {
        struct ListNode*n3=n2->next;//n3用于记录当前操作项的下一项 
        //迭代
        n2->next=n1;
        //赋值
        n1=n2;
        n2=n3;
        if(n3)
        {
            n3=n3->next;
        }
    }
    return n1;
}

---

三.链表的中间结点

3.1.题目链表:链表的中间结点

 3.2.思路分析

思路：(快慢指针）

快指针走俩步，慢指针走一步

1.偶数个结点：fast->next=NULL

2.奇数个结点：fast=NULL

return slow

 3.3.代码

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode*fast=head;
    struct ListNode*slow=head;
    while(fast!=NULL&&fast->next!=NULL)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

---

四.链表中倒数第K个结点 

4.1.题目链接：链表中倒数第K个结点

4.2.思路分析 

思路：(双指针）

1.在头节点前面建立伪节点

2.规律：快指针先走到第k个节点，随后前后指针一起走，当前指针走到结尾null节点时，慢指针即指向倒数第k个节点

• fast 先向右移动 k 位，此时 index(fast) - index(slow) = k
• fast和 slow一起向右移动，直到 fast抵达边界
• 由于index(fast) - index(slow) = k，所以index(slow) = index(fast) - k = length - k。也就是slow指针移动到了倒数第 k 个位置

1.快指针先移动k步

 2.fast和slow同时一起向右走，直到fast抵达边界

 4.3.代码

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    if(pListHead==NULL)
    {
        return NULL;
    }
    struct ListNode*fast=pListHead;
    struct ListNode*slow=pListHead;
    //fast走k步
    while(k--)
    {
        if(fast==NULL)
        {
            return NULL;
        }
        fast=fast->next;
    }
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return slow;
    // write code here
}

---

五.合并俩个链表

5.1.题目链接：合并两个有序链表

 5.2.思路分析

思路：这道题和上面的合并俩个数组的思路有几分相似，只不过一个是数组，一个是链表

依次进行尾插即可，还得判断未完成尾插的链表要进行再次判断，然后尾插到其后即可。

1.带哨兵位：创建一个带有哨兵位的新链表，然后最后记得释放

2.不带哨兵位：要考虑俩种情况

                      1.其中一个链表为空，返回另一个链表

                      2.头部尾插，需要另作判断条件

3.malloc和free结合利用

由于前面开辟一个一个新结点，malloc需要与free配用，所以到最后得释放 

 

创建一个哨兵位结点，然后依次尾插即可 

 5.3.代码

 不带哨兵位
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    struct ListNode*cur1=list1;
    struct ListNode*cur2=list2;
    struct ListNode*head=NULL;
    struct ListNode*tail=NULL;
    while(cur1&&cur2)
    {
        if(cur1->val<cur2->val)
        {
            //尾插
            if(head==NULL)
            {
                head=tail=cur1;
            }
            else
            {
                tail->next=cur1;
                tail=tail->next;
            }
            cur1=cur1->next;
        }
        else
        {
             //尾插
            if(head==NULL)
            {
                head=tail=cur2;
            }
            else
            {
                tail->next=cur2;
                tail=tail->next;
            }
            cur2=cur2->next;
        }
    }
    if(cur1)
    {
        tail->next=cur1;
    }
    if(cur2)
    {
        tail->next=cur2;
    }
    return head;
}
 
 
 
 
//带哨兵位
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode*cur1=list1;
    struct ListNode*cur2=list2;
    struct ListNode*guard=NULL,*tail=NULL;
    guard=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
    tail->next=NULL;
    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)
    {
        tail->next=cur1;
    }
    if(cur2)
    {
        tail->next=cur2;
    }
    struct ListNode*head=guard->next;
    free(guard);
    guard=NULL;
    return head;
}

---

六.分割链表

6.1.题目链接：链表分割

 6.2.思路分析

思路：尾插

创建俩个带有哨兵位的链表，malloc和free匹配使用

1.小于x：放在lGuard链表中

2.大于x：放在gGuard链表中

然后俩个链表连接，返回lGuard的头结点就可以

1.初始位置是这样的 

 2.小于x，插入到lGuard链表中，大于x，插入到gGuard链表中

最后将gTail接到lTail后面，然后给gTail置空，因为带有哨兵位，所以lGuard->next给head，然后返回head。

中间gTail->next=NULL,一定要置空，不然本身的5的next是指向2的，必须给置空

 6.3.代码

{
    struct ListNode*gGuard,*gTail,*lGuard,*lTail;
    gGuard=gTail=(struct ListNode*)malloc(sizeof(struct ListNode));
    lGuard=lTail=(struct ListNode*)malloc(sizeof(truct ListNode));
    gTail->next=NULL;
    lTail->next=NULL;
    truct ListNode*cur=head;
    while(cur)
    {
        if(cur->val<x)
        {
            lTail->next=cur;
            lTail=lTail->next;
        }
        else
        {
            gTail->next=cur;
            lTail=lTail->next;
        }
        cur=cur->next;
    }
    lTail->next=gGuard->next;
    gTail->next=NULL;
    head=lGuard->next;
    free(lGuard);
    lGuard=NULL;
    free(gGuard);
    gGuard=NULL;
    return head;
}

---

七.回文链表

7.1.题目链接：回文链表

 7.2.思路分析

• 第一步：找到中间结点(见以上（三.链表的中间位置））
• 第二步：从中间结点开始，对后半段进行逆置 （见以上（二.反转链表））
• 第三步：前半段和后半段进行数据判断是否相等即可

剩下就是代码实现了

7.3.代码实现

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode*fast=head;
    struct ListNode*slow=head;
    while(fast!=NULL&&fast->next!=NULL)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}
 
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode*n1=NULL;
    struct ListNode*n2=head;
    while(n2)
    {
        struct ListNode*n3=n2->next;
        //迭代
        n2->next=n1;
        //赋值
        n1=n2;
        n2=n3;
        if(n3)
        {
            n3=n3->next;
        }
    }
    return n1;
}
 
bool isPalindrome(struct ListNode* head)
{
     //找到中间结点
    struct ListNode*mid=middleNode(head);
    //从中间结点后反转
    struct ListNode*rhead=reverseList(mid);
    while(rhead)
    {
        if(head->val!=rhead->val)
        {
            return false;
        }
        else
        {
            head=head->next;
            rhead=rhead->next;
        }
    }
    return true;
}

---

八.相交链表

8.1.题目链接：相交链表

8.2.思路分析 

第一步：求俩个链表的长度

第二步：长的链表先走差距步 (链表长度差距）

第三步：同时走，第一个地址相同的就是交点 

8.3.代码实现

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode*curA=headA;
    struct ListNode*curB=headB;
    int lenA=1;
    int lenB=1;
    while(curA)
    {
        lenA++;
        curA=curA->next;
    }
    while(curB)
    {
        lenB++;
        curB=curB->next;
    }
    curA=headA;
    curB=headB;
    int gap=abs(lenA-lenB);//abs取的是绝对值
    struct ListNode*longList=headA,*shortList=headB;//假设a长b段
    if(lenA<lenB)//如果a短b长
    {//就改变
        longList=headB;
        shortList=headA;
    }
    while(gap--)
    {
        longList=longList->next;
    }
    while(longList!=shortList)
    {
        longList=longList->next;
        shortList=shortList->next;
    }
    return longList;
}

---

九.环形链表

9.1.题目链接：环形链表

 9.2.思路分析

快慢指针：

结论：快指针走俩步，慢指针走一步，存在环形，那就肯定会相遇。

9.3.代码实现

bool hasCycle(struct ListNode *head) 
{
    struct ListNode *slow=head;
    struct ListNode *fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            return true;
        }
    }
    return false;
    
}

十.环形链表2

10.1.题目链接：环形链表2

 10.2.思路分析

首先由上个 环形链表 题目中可以得到

结论1：快指针走俩步，慢指针走一步，存在环形，那就肯定会相遇。

结论2：一个指针从相遇点开始走，一个指针从链表开始走，它们会从入口点相遇

 10.3.代码实现

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode *slow=head;
    struct ListNode *fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            struct ListNode *meet=slow;//一个指针从相遇点出发
            struct ListNode *start=head;//一个指针从起始点出发
            while(meet!=start)//它俩一定再入口点相遇
            {
                meet=meet->next;
                start=start->next;
            }
            return meet;
        }
    }
    return NULL;
}

---

就算失败，我也想知道，自己倒在距离终点多远的地方-------------《长安的荔枝》