【数据结构与算法】之8道顺序表与链表典型编程题心决！

                                                                                个人主页：秋风起，再归来~

                                                                                            数据结构与算法                             

                                                                       个人格言：悟已往之不谏，知来者犹可追

                                                                                        克心守己，律己则安！

目录

1、顺序表

1.1 合并两个有序数组

1.2 原地移除数组中所有的元素val

2、链表

2.1 移除链表元素

2.2 反转链表

2.3 合并两个有序链表

2.4 链表的中间节点

2.5 环形链表的约瑟夫问题

2.6 分割链表

3、完结散花

1、顺序表

1.1 合并两个有序数组

题目描述：

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

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

 解题代码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int tail=nums1Size-1;
    int p1=m-1;
    int p2=n-1;
    while(p1>=0&&p2>=0)
    {
        if(nums1[p1]>nums2[p2])
        {
            nums1[tail--]=nums1[p1--];
        }else{
            nums1[tail--]=nums2[p2--];
        }
    }
    if(p1<0)
    {
        while(p2>=0)
        {
             nums1[tail--]=nums2[p2--];
        }
    }
}

1.2 原地移除数组中所有的元素val

题目描述：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0 1,3,0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

OJ链接移除元素

 解题代码：

int removeElement(int* nums, int numsSize, int val) {
    if(numsSize<=0||nums==NULL)
    return 0;
    int cur=0;//用cur去遍历原数组
    int newNums=0;
    while(numsSize--)
    {
        if(nums[cur]==val)
        {
            cur++;
        }else{
            nums[newNums++]=nums[cur++];
        }
    }
    return newNums;
}

2、链表

2.1 移除链表元素

题目描述：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

OJ链接：移除链表元素

解题代码： 

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    if(head==NULL)
    return NULL;
    ListNode* newHead=(ListNode*)malloc(sizeof(ListNode));//创建一个带哨兵卫的头结点
    ListNode* newTail=newHead;
    ListNode* cur=head;
    while(cur)
    {
        if(cur->val==val)
        {
            cur=cur->next;
        }else{
            newTail->next=cur;
            newTail=newTail->next;
            cur=cur->next;
        }
    }
    newTail->next=NULL;
    return newHead->next;
}

2.2 反转链表

题目描述：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

题目链接：反转单链表

解题代码：

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)
    return NULL;
    ListNode* n1,*n2,*n3;
    n1=NULL;
    n2=head;
    n3=head->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        {
            n3=n3->next;
        }
    }
    return n1;
}

2.3 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

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

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    
    ListNode* newHead,*newTail;
    newTail=newHead=(ListNode*)malloc(sizeof(ListNode));
    ListNode* l1=list1;
    ListNode* l2=list2;
    while(l1&&l2)
    {
        if((l1->val)<(l2->val))
        {
            newTail->next=l1;
            l1=l1->next;
        }else{
            newTail->next=l2;
            l2=l2->next;
        }
        newTail=newTail->next;
    }
    if(l1)
    {
        newTail->next=l1;
    }else{
        newTail->next=l2;
    }
    return newHead->next;
}

2.4 链表的中间节点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

• 链表的结点数范围是 [1, 100]
• 1 <= Node.val <= 100

OJ链接链表的中间节点

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

2.5 环形链表的约瑟夫问题

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。

下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

数据范围： 1≤n,m≤10000

进阶：空间复杂度O(1)，时间复杂度 O(n)

   OJ链接：环形链表的约瑟夫问题

typedef struct ListNode ListNode;
ListNode* byNode(int x)
{
    ListNode* node=(ListNode*)malloc(sizeof(ListNode));
    if(node==NULL)
    {
        exit(1);
    }
    node->val=x;
    return node;
}
ListNode* creatCircle(int x)
{
    ListNode* head=(ListNode*)malloc(sizeof(ListNode));//创建头结点
    if(head==NULL)
    {
        exit(1);
    }
    ListNode* tail=head;
    for(int i=1;i<=x;i++)
    {
        tail->next=byNode(i);
        tail=tail->next;
    }
    tail->next=head->next;
    return tail;
}

int ysf(int n, int m ) {
    // write code here
    //创建循环链表并返回尾节点
    ListNode* prev=creatCircle(n);
    ListNode* cur=prev->next;
    int count=1;//报数
    while(cur!=cur->next)
    {
        if(count==m)
        {
            prev->next=cur->next;
            free(cur);
            cur=prev->next;
            count=1;//重置为1
        }else {
            prev=cur;
            cur=cur->next;
            count++;
        }
    }
    return cur->val;
}

2.6 分割链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

OJ链接：分割链表

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
    if(head==NULL)
    {
        return NULL;
    }
    //创建两个头结点
    ListNode* lessHead=(ListNode*)malloc(sizeof(ListNode));
    if(lessHead==NULL)
    {
        exit(1);
    }
    ListNode* greaterHead=(ListNode*)malloc(sizeof(ListNode));
    if(greaterHead==NULL)
    {
        exit(1);
    }
    ListNode* lessTail=lessHead;
    ListNode* greaterTail=greaterHead;
    lessHead->next=greaterHead->next=NULL;
    ListNode* cur=head;
    while(cur)
    {
        if(cur->val<x)
        {
            lessTail->next=cur;
            lessTail=lessTail->next;
        }else{
            greaterTail->next=cur;
            greaterTail=greaterTail->next;
        }
        cur=cur->next;
    }
    lessTail->next=greaterHead->next;
    greaterTail->next=NULL;
    return lessHead->next;
}

3、完结散花

好了，这期的分享到这里就结束了~

如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~

我们下期不见不散~~

​​​​文章来源地址https://www.toymoban.com/news/detail-850926.html

到了这里，关于【数据结构与算法】之8道顺序表与链表典型编程题心决！的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！