9、尾插，和任意位置插入

//头删void erasePopFront(SeqList* SL) {	for (int i = 1; i < SL->count; i++) {		SL->data[i - 1] = SL->data[i];	}	SL->count -= 1;	return;}//尾删void erasePopBack(SeqList* SL) {	assert(SL);	assert(SL->count);	SL->count -= 1;	return;}//任意位置删除void erase(SeqList* SL, int pos) {	if (pos < 0 && pos >= SL->count) return;	for (int i = pos; i < SL->count - 1; i++) {		SL->data[i] = SL->data[i + 1];	}	SL->count -= 1;	return;}

class PalindromeList {public:    bool chkPalindrome(ListNode* A) {        int arr[1000], i = 0;        ListNode* p = A;        while (p) {            arr[i++] = p->val;            p = p->next;        }        int left = 0, right = i - 1;        while(left <= right) {            if(arr[left++] != arr[right--]) return false;        }        return true;    }};

class Solution {public:    ListNode* removeElements(ListNode* head, int val) {        ListNode* newhead = NULL, *tail = NULL, *p = head;        while(p){            if(p->val != val){                if(newhead == NULL) {                    newhead = tail = p;                }else{                    tail->next = p;                    tail = tail->next;                }            }            p = p->next;        }        if(tail) tail->next = NULL;        return newhead;    }};

typedef int SLTDataType;typedef struct SListNode {	SLTDataType data;	struct SListNode* next;}SLTNode;

class Solution {public:    int removeDuplicates(vector<int>& nums) {        int src = 1, dst = 0;        while(src < nums.size()){               if(nums[src] == nums[dst]){                src += 1;            }            else{                nums[++dst] = nums[src++];            }        }        return dst + 1;    }};

线性表

线性表：线性表是具有逻辑结构是连续，物理结构不一定是连续的一类数据结构的集合。销毁

void clearSeqList(SeqList* SL) {	if (SL == NULL) return;	if (SL->data) free(SL->data);	SL->data = NULL;	SL->count = SL->size = 0;	return;}

3、相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

题目分析

将长的链表先截成和短的链表的长度，因为是后面部分相交，挨个比较直到两个指针的地址相等为相交结点

class Solution {public:    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {        ListNode* p = headA;        int lenA = 0, lenB = 0;        while(p){            p = p->next;            lenA += 1;        }        p = headB;        while(p){            p = p->next;            lenB += 1;        }        int length = abs(lenA - lenB);        ListNode* longlist = headA;        ListNode* shortlist = headB;        if(lenA < lenB){            longlist = headB;            shortlist = headA;        }        while(length--){            longlist = longlist->next;        }        while(longlist != shortlist){            longlist = longlist->next;            shortlist = shortlist->next;        }        return shortlist;    }};

7、尾删，和任意位置删除。插入

5、合并两个有序链表

• 题目分析

5、初始化

void initSeqList(SeqList* SL) {	SL->data = NULL;	SL->count = SL->size = 0;	return;}

2、然后同一。链表的销毁

存储链表的下一个结点，然后进行 free

void SListDestroy(SLTNode** pphead){	assert(pphead && *pphead);	SLTNode* pcur = *pphead;	while (pcur)	{		SLTNode* next = pcur->next;		free(pcur);		pcur = next;	}	*pphead = NULL;}

（三）链表的例题分析

1、环形链表||

https://leetcode.cn/problems/linked-list-cycle-ii/description/

题目分析

在相遇之后，相遇点和头结点到环的起始点的距离相等，用两个指针从这两个位置同时出发，直到相遇。

9、尾插，和任意位置插入。
插入操作需要整体后移 ： 从后面像前面遍历，反之会产生数据的覆盖。环形链表||

• 题目分析

9、随机链表的复制

https://leetcode.cn/problems/copy-list-with-random-pointer/description/

题目分析

如下图

步骤一 ： 添加复制的结点

步骤二： 给random 赋值
步骤三： 断开原来的链表和拷贝链表

class Solution {public:    Node* BuyNode(int val) {        Node* p = (Node*)malloc(sizeof(Node));        p->val = val;        p->next = p->random = NULL;        return p;    }    void AddNode(Node* head) {        Node *pcur = head, *next;        while (pcur) {            next = pcur->next;            Node* node = BuyNode(pcur->val);            pcur->next = node;            node->next = next;            pcur = next;        }        return;    }    Node* SetRandom(Node* head) {        Node* pcur = head;        while (pcur) {            Node* temp = pcur->next;            if (pcur->random) {                temp->random = pcur->random->next;            }            pcur = pcur->next->next;        }        return head;    }    Node* getNewLinkList(Node* head) {        Node *newHead, *tail;        Node* pcur = head;        newHead = tail = head->next;        while (pcur) {            pcur->next = tail->next;            if (tail->next) {                tail->next = pcur->next->next;                tail = tail->next;            }            pcur = pcur->next;        }        // tail->next = NULL; // 确保新链表的尾部正确        return newHead;    }    Node* copyRandomList(Node* head) {        if (head == NULL)            return NULL;        AddNode(head);        head = SetRandom(head);        head = getNewLinkList(head);        return head;    }};

小结：无需多言，值得反复学习

结束语

好了，小编也要睡觉了，下一篇小编会带来双向链表的博文。
方法二 ： 中间结点后面的结点进行反转，切记反转链表反转的是指针的方向，数据位置没有变。顺序表分为动态顺序表和静态顺序表，为了防止空间过度浪费，空间不足，我们一般采用动态顺序表。链表的初始化

2、扩容

采用 realloc 进行扩容，考虑到原来的容量为 0， 不可单纯的进行乘二

void SLCheckCapacity(SeqList* SL) {	if (SL->count == SL->size) {		int n = SL->count == 0 ? 4 : 2 * SL->size;		SLdataType* temp = (SLdataType*)realloc(SL->data, sizeof(SLdataType) * n);		if (temp == NULL) {			perror("realloc fail\n");			exit(1);		}		SL->data = temp;		SL->size *= n;	}	return;}

4、合并两个有序数组

https://leetcode.cn/problems/merge-sorted-array/

小结 ： 采用两个指针分别指向两个数组的末尾，依次将数据放在数组一。环形链表

https://leetcode.cn/problems/linked-list-cycle/

题目分析

用快慢指针，如果有环，那么快指针就会追上慢指针。链表

（一）链表的结构定义

这里也用的typedef 可以使得我们的数据类型更加灵活。

//尾插void SLTPushBack(SLTNode** pphead, SLTDataType x) {	SLTNode* node = BuyNode(x);	if (*pphead == NULL) {		*pphead = node;		return;	}	SLTNode* p = *pphead;	while (p->next) p = p->next;	p->next = node;	return;}//头插void SLTPushFront(SLTNode** pphead, SLTDataType x) {	SLTNode* node = BuyNode(x);	if (*pphead == NULL) {		*pphead = node;		return;	}	node->next = *pphead;	*pphead = node;	return;}//任意位置之前插入，采用双指针的方式void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {	assert(pos);	assert(*pphead);	SLTNode* node = BuyNode(x);	if (*pphead == pos) {		node->next = pos;		*pphead = node;		return;	}	SLTNode* fast = (*pphead)->next, * slow = *pphead;	while (fast != pos) {		fast = fast->next;		slow = slow->next;	}	slow->next = node;	node->next = fast;	return;}//任意位置之后插入方式会大大简便void SLTInsertAfter(SLTNode* pos, SLTDataType x) {	assert(pos);	SLTNode* node = BuyNode(x);	node->next = pos->next;	pos->next = node;	return;}

3、但是创建数组的时间复杂度为O（n)，不可以通过。链表篇

• 线性表
• 一、尾删和任意位置删除。

（一）顺序表的结构定义

typedef int SLdataType;typedef struct SeqList {	SLdataType* data;	int count, size;}SeqList;

用到typedef, 可以使得我们的顺序表存放数据的类型更加的灵活。
while 循环可以用 && 也可以用 || 采用两种代码实现

采用 || 的方式实现

class Solution {public:    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {        int l1 = m - 1, l2 = n - 1, l3 = m + n - 1;        while (l1 >= 0 || l2 >= 0) {            if (l2 < 0 || (l1 >= 0 && nums1[l1] > nums2[l2]))                nums1[l3--] = nums1[l1--];            else                nums1[l3--] = nums2[l2--];        }    }};

或者采用 && 的方式实现

class Solution {public:    void merge(vector<int>& nums1, int m, vector<int>& nums2, 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--];            else                nums1[l3--] = nums2[l2--];        }        while (l2 >= 0) {            nums1[l3--] = nums2[l2--];        }    }};

(四）顺序表的弊端

1、创建两个指针Node* head, * tail;
3、链表的删除

4、顺序表的插入删除操作的时间复杂度为O（n）
2、任意位置插入时采用双指针定向移动。

2、链表的销毁

（三）链表的例题分析

• 1、反转链表

https://leetcode.cn/problems/reverse-linked-list/

题目分析

class Solution {public:    ListNode* reverseList(ListNode* head) {        if(head == NULL) return NULL;        ListNode* pre = NULL, * cur = head, * Next = head->next;        while(cur){            cur->next = pre;            pre = cur;            cur = Next;            if(!cur) break;            Next = Next->next;        }        return pre;    }};

小结：与另外新建一个链表的方式不同，这种算法可以在原来的链表上进行处理就能达到反转链表的效果。插入

插入操作分为头插、

数据结构：顺序表、链表的中心结点

• 题目分析

4、

问题一 ： 快指针为什么一定会追上慢指针
因为每次追逐两个指针的距离都会减一

问题二：快指针每次可以走2， 3， 4 ~步吗
下面我们以快指针每次走三步为例，结果是一定相遇，其他推理结论相同

class Solution {public:    bool hasCycle(ListNode *head) {        ListNode* fast ,* slow;        fast = slow = head;        while(fast && fast->next){            fast = fast->next->next;            slow = slow->next;            if(fast == slow) return true;        }        return false;    }};

小结：上面的文章里面，我们用快慢指针找中间结点，现在又多了一种新的用法，用来判断是否有环。链表的删除

链表的插入分为头删、

3、尾插和任意位置插入。环形链表

• 题目分析

8、链表的插入

3、用 malloc 开辟空间，返回malloc 的下一个结点， 记得要free；

5、相交链表

• 题目分析

7、链表的初始化

同顺序表相同，链表在初始化时也采取泛型的方式，适应多种数据类型。

class Solution {public:    ListNode* middleNode(ListNode* head) {        ListNode* fast, *slow;        fast = slow = head;        while(fast && fast->next){            fast = fast->next->next;            slow = slow->next;        }        return slow;    }};

小结： 用快慢指针有很多好处，这道题的中间值就是一个

4、如果感兴趣的话记得要给博主一个关注哦，不然就再也找不到啦，小伙伴们周末快乐！