爱上数据结构：顺序表和链表

一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使
用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表的OJ题

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

27. 移除元素 - 力扣（LeetCode）https://leetcode.cn/problems/remove-element/description/

int removeElement(int* nums, int numsSize, int val) {int scr=0,dst=0;while(scr<numsSize){if(nums[scr]==val){scr++;}else{nums[dst]=nums[scr];scr++;dst++;}}return dst;
}

在原数组上进行修改，等于val的跳过，不赋值。反之则赋值。

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

26. 删除有序数组中的重复项 - 力扣（LeetCode）https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

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

对于这道题先处理特殊情况，如果numssize==0，则该数组没元素返回0。可以采用双指针法来实现，定义快慢指针，fast不等于fast-1对应下标的内容则让该fast对应的赋值给slow，再将slow++，

反之则就只让fast++，最后返回slow，slow前的数据都只出现了一次。

3.合并两个有序数组

88. 合并两个有序数组https://leetcode.cn/problems/merge-sorted-array/

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int l1=m-1,l2=n-1,l3=m+n-1;while(l1>=0&&l2>=0){if(nums1[l1]>nums2[l2]){nums1[l3]=nums1[l1];l3--;l1--;}else{nums1[l3]=nums2[l2];l3--;l2--;}}while(l2>=0){nums1[l3]=nums2[l2];l3--;l2--;}
}

按照题目要求本题本来就是要进行升序排序，对大的数据进行尾插操作，值得注意的是为什么需要对l2进行第二次循环呢？

因为&& 前真才会判断后面的，而如果前面就是假则直接判假跳过后面的了，所以需要对l2进行判断。

三、链表OJ题

在之前就已经写过一些有关链表的OJ题了，感兴趣的朋友可以去这个链接观看！！

学习c语言：单链表的应用-CSDN博客文章浏览阅读899次，点赞31次，收藏32次。单链表OJ题https://blog.csdn.net/bskmns/article/details/136591727?spm=1001.2014.3001.5501现在要对链表OJ题做些补充，准备发车了哦！！

1.链表分割

链表分割_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

对于这个题，可以通过创建两个链表来进行分割，将小于x的数据尾插到less链表中，将大于x的数据尾插到great链表中。然后将less链表的未结点与great的头节点的next连接到一起，使链表连在一起，再将greattail置为空。返回lesshead->next.

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode*greatHead,*greattail,*lessHead,*lesstail,*cur;greatHead=greattail=(struct ListNode*)malloc(sizeof(struct ListNode));lessHead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));cur=pHead;while(cur){if(cur->val<x){lesstail->next=cur;lesstail=cur;cur=cur->next;}else{greattail->next=cur;greattail=cur;cur=cur->next;}}    lesstail->next=greatHead->next;greattail->next=nullptr;return lessHead->next;}
};

2.链表的回文结构

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

对于这个题，首先要找它的中间节点，使用快慢指针找中间节点，然后将slow后的链表进行逆置，然后将A与slow进行比较，以slow不等于A作为循环，如果值不相等就返回false，如果A的下一个等于slow就返回true，如果不是就将slow和A移到下一个。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code herestruct ListNode* slow=A;struct ListNode* fast=A;while(fast && fast->next){slow=slow->next;fast=fast->next->next;}struct ListNode* head=slow;while(head){struct ListNode*next=head->next;head->next=slow;slow=head;head=next;}head=A;while(slow!=A){if(A->val!=slow->val){return false;}if(A->next==slow){return true;}else{slow=slow->next;A=A->next;}}return true;;}
};

三、相交链表

160. 相交链表 - 力扣（LeetCode）https://leetcode.cn/problems/intersection-of-two-linked-lists/两个链表找相交节点，如果一个链表为空则不存在相交节点，设置pa pb遍历链表，while循环如果pa不等于pb就进入循环，使pa和pb向后遍历，如果为空就返回headB headA，不为空就置为下一个。最后返回pa。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {if(headA==NULL||headB==NULL){return NULL;}struct ListNode* pa=headA,*pb=headB;while(pa!=pb){pa=pa==NULL?headB:pa->next;pb=pb==NULL?headA:pb->next;}return pa;
}

四、环形链表

141. 环形链表 - 力扣（LeetCode）https://leetcode.cn/problems/linked-list-cycle/在这个题中要判断该链表是否有环，可以通过快慢指针来进行实现，while循环fast&&fast->next

fast=fast->next->next slow=slow->next,每次fast多走一步，所以链表只要有环就一定可以实现判断（当slow==fast时返回true），否则返回false。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode* slow=head,*fast=head;while(fast &&fast ->next){fast=fast->next->next;slow=slow->next;if(slow==fast){return true;}}return false;
}

好了，本期的内容到此结束，谢谢大家观看啊！！！

学习数据结构任重而道远，加油啊各位！！！