当前位置：首页 > news >正文

【初阶数据结构】顺序表和链表算法题（上）

news 来源：原创 2024/9/21 2:46:45

顺序表和链表算法题

1.顺序表
- 1.1移除元素
- 1.2删除有序数组中的重复项
- 1.3合并两个有序数组
2.链表
- 2.1移除链表元素
- 2.2反转链表
- 2.3链表的中间结点

1.顺序表

1.1移除元素

在这里插入图片描述
注意：返回的是元素个数，while循环不要少了等号

//https://leetcode.cn/problems/remove-element/description///
int removeElement(int* nums, int numsSize, int val) 
{int src = 0, dst = 0;while (src < numsSize){if (num[src] == val){src++;}else {nums[dst++] = nums[src++];//把src(走的快的值）给dst}}//此时，dst指向的位置就是要返回的有效个数
}

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

在这里插入图片描述

题目信息：非严格递增序列，双指针法比较前后两个元素即可

int removeDuplicates(int* nums, int numsSize) {int src = 0;int dest = 1;while (dest < numsSize){if (nums[src] != nums[dest]){src++;nums[src] = nums[dest];}dest++;}return ++src;//因为src是从0开始的，所以需要加1，//但又因为，如果后置++，return完之后才++，所以前
}

1.3合并两个有序数组

在这里插入图片描述

思路：两个指针依次从尾部向前遍历，谁大把谁放到nums1的尾部（若前方开始比较谁小，那需要新建一个数组）
最后出循环的时候l2和l3只可能有一个小于0，若是l2，说明nums2没有遍历完，需要将剩下的元素赋值给nums1—若是l3，则直接返回nums1即可

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int l1 = m - 1;int l2 = n - 1;int l3 = m + n - 1;while (l1 >= 0 && l2 >= 0) // 不知道是&&还是||带入试试{if (nums1[l1] > nums2[l2]){nums1[l3--] = nums1[l1--];//谁大谁给s1}else{//要不l1==l2,yaobul2>l1nums1[l3--] = nums2[l2--];}}//跳出while有两种情况：要不L1<0(需要处理)，L2<0不用处理while (l2 >= 0){nums1[l3--] = nums2[l2--];}
}

2.链表

2.1移除链表元素

在这里插入图片描述

不是开辟空间的深拷贝，而只是定义了指向同一结点的指针
在最后需要先判断newtail是否为空,否则链表为空链表时会报错.
再将其中的next指针置为空,否则可能会出现循环.

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
//创建一个新链表newnode,把值不为val的值尾插进去
//pcur遍历原链表
typedef struct ListNode ListNode;
ListNode* removeElements(ListNode* head, int val) {//创建新链表ListNode* newhead = NULL;ListNode* newtail = NULL;//遍历原链表ListNode* pcur = head;while (pcur){   //找值不为val的节点，往新链表进行尾插 前val相当于dataif (pcur->val != val) {//链表头结点为空if (newhead == NULL) {newhead = newtail = pcur;}else {//链表头结点不为空newtail->next = pcur;newtail = newtail->next;}}pcur = pcur->next;}if (newtail)//防止新链表为空，如果直接下一行就报错newtail->next = NULL;return newhead;
}

2.2反转链表

在这里插入图片描述
思路

2.3链表的中间结点

在这里插入图片描述

快慢指针法的应用
注意为偶数时返回第二个节点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///快慢指针的应用，快1慢2
typedef struct ListNode ListNode;
ListNode* middleNode(ListNode* head) {ListNode* slow, * fast;slow = fast = head;while (fast && fast->next)//两个都满足才进入循环{slow = slow->next;fast = fast->next->next;//此时slow指向的结点刚好就是中间结点}return slow;
}