顺序表和链表对应的经典算法-拓冰建站

一，移除元素

思路：定义一个循环遍历数组，如果遇到的不是val就记录下来这个元素，如果不是就跳过

定义两个指针，一个用于保留非val元素，一个用于遍历nums

int removeElement(int* nums, int numsSize, int val)
{int*pst=nums;//用于遍历的指针int*prev=nums;//用于保留元素的指针int size = 0;//被保留下来的元素个数for(int i=0;i<numsSize;i++ ){if(pst[i]!=val){prev[size]=pst[i];size++;}}return size;//题目要求只要返回保留的元素个数即可
}

二，合并两个有序数组

思路：边合并边排序

思路一：指定三个标记

L1=m-1;

L2=n-1;

L3=m+n-1;

从后向前比较L1对应的数据与L2对应的数据的大小，谁大就把谁放在L3处，每次比较完，大的数据对应的标记向前走一个，L3也向走一个，最后会有两种情况

一种是L1对应的数据全部放入后三个空位，此时L1已经走到头部对应1的位置，L2还没有全部放入大的数组里面，因为数组是非递减排列的，所以最后只需将剩下L2所有元素一一放入大数组。

一种是L2对应的数据全部放入后三个空位，此时在大数组所有元素均已有序。

void merge(int*nums1,int nums1Size,int m,int*nums2,int nums2Size,int n)
{int L1=m-1;int L2=n-2;int L3=m+m-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)//此时L1对应数据全部放入尾部，因为两数组均是递增，所以直接将nums2放入尾部即可{nums1[L3]=nums2[L2];L3--;L2--;}
}

三，环形链表的约瑟夫问题

分析：

本题需要有一个能够循环遍历的链表，并且每次数到第m个数都需要删除该节点。

int ysf(int n, int m ) 这个是题目给我们的函数，按照题目意思，我们需要在此函数里循环遍历链表，删除m节点；

首先我们需要自己创建一个函数，这个函数能够将每个人包装成节点，其次还需要一个函数可以将每个节点连接起来。

包装节点函数可以这样写

#include<stdio.h>
#include<stdlib.h>
typedef struct ListNode ListNode;//将结构体重命名方便使用ListNode*Newnode(int m)
{ListNode*newnode=(ListNode*)malloc(sizeof(ListNode));if(newnode==NULL){perror("newnode");//如果开辟空间失败及时报错exit(1);//退出}//开辟成功，将m值放入放入节点newnode->val=m;newnode->next=NULL;//将指向下一节点的指针置空避免野指针return newnode;
}

有了包装节点的函数，

还需一个可以将其连接起来的函数

ListNode*Contact(int n) //一共有n个人，也就是n个节点
{ListNode*phead=Newnode(1);//先定一个头节点作为链表的头指向第一个人ListNode*cur=phead;//在cur中保留一份链表头节点int i = 0;for(i=2;i<=n;i++)从第二个人开始链结{ListNode*next = Newnode(i);cur->next=next;//使cur链接下一节点cur=cur->next;//使cur向后移动，作为新创建的节点}//到这里cur已成为尾节点cur->next=phead;//使尾节点的下一节点为头节点，成为循环链表return cur;//返回尾节点}

这里有个疑惑，为什么我不返回头节点，而返回一个尾节点呢，因为在最后的主函数中要循环链表，如果返回头节点那么还没有循环时就已经是第一个人了，刚向下走一步就已经是第二个人了，不方便计数。

下面是主函数的定义

int ysf(int n,int m)
{int count = 1;//用来计数第几个人ListNode*prev=Newnode(m); //prev为尾节点ListNode*pcur=prev->next;//pcur为头节点while(pcur->next!=cpur)//开始循环，终止条件是下一个节点指向自己，说明只剩一个人{if(count==m){//此时pcur为要删除的节点prev->next=pcur->next//使前置节点prev的下一节点指向pcur后一节点free(pcur);//删除当前节点pcur=prev->next;//使pcur重新指向被删除节点的后一节点}else{prev=pcur;//prev始终为pcur的前一节点pcur=pcur->next;count++; //既然不是要删的节点，就pcur指向下一个节点，count增加}}
//最后只剩下一人，返回它对应的人return pcur->val              
}

最后将三段代码合并即可

四，链表的中间节点

本题可以有两个思路，只介绍思路二。

思路一：寻常方法一一遍历计算节点个数找到中间节点

思路二：算法思想:快慢指针法，定义两个指针，当快指针走到尾节点或者NULL，慢指针刚好走到中间节点。

如何使快指针走到尾，慢指针刚好是中间节点呢？可以使快指针每次走两步，慢指针每次走一步。


typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode*fast,*slow;fast=slow=head;  //两个指针均从头开始while(fast&&fast->next){slow=slow->next;//一次走一步fast=fast->next->next;//一次走两步}return slow;
}

五，合并两个有序链表

分析：

由两个链表合并为一个链表，我们可以创建第三个链表来存放。

定义三个指针，其中两个指针去遍历链表，哪个指针指向的节点较小，就将其放入第三个指针指向指向的链表中，被放入节点的指针向后移动一个单位。

typedef struct ListNode ListNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1==NULL){return list2;}if(list2==NULL){return list1;}ListNode*L1=list1;ListNode*L2=list2;ListNode*newhead=NULL;ListNode*newptail=newhead;while(L1&&L2){if(L1->val < L2->val){if(newhead==NULL)// 如果新链表还没有放入节点，直接是其头尾指针指向第一个节点{newhead=newptail=L1;L1=L1->next;//被放入节点的指针向后移动}else{       //新链表中已经放入元素，直接尾节点指向被放入的节点，//使被放入的节点为新的尾节点。newptail->next = L1;newptail = newptail->next;L1=L1->next;}}else{if(newhead==NULL){newhead=newptail=L2;L2 = L2->next;}else{newptail->next = L2;newptail = newptail->next;L2=L2->next;}}}if(L1) //如果L1指向的链表还有元素未被放完，直接其尾插新的链表{newptail->next = L1;}if(L2) //如果L2指向的链表还有元素未被放完，直接其尾插新的链表{newptail->next = L2;}return newhead;
}

六，反转链表

分析：

一般单链表的性质就是单项连接不循环的，先要反转链表可能会不太好想。

这里有一种非常让人难以想到的方法：

可以定义三个指针，分别指向NULL，第一个节点和第三个节点。

以第二个指针不为空，也就是走到最后一个节点就结束为条件

每循环一次就是第一个指针指向第二个指针的节点，

然后第二个指针指向第三个指针的节点，最后第三个指针向后移动一个单位

这样一来就可以使链表反向。上面只展示循环的一个过程啦，后面的过程照着这样循环，

最后n2和n3都会为空，而n1会变成指向5节点的指针。

下面是代码：短小精悍

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

七，移除链表元素

思路：

这题可以创建一个新的链表，在创建一个指针指向原来的链表，遍历原来的链表，只要是要删除的值就跳过，如果不是要删除的值，就把对应的节点尾插给新链表

typedef struct ListNode ListNode;struct ListNode* removeElements(struct ListNode* head, int val) {if(head==NULL){return  head;}ListNode*NewHead=NULL;ListNode*NewTail=NULL;ListNode*pcur=head;while(pcur){if(pcur->val!=val){//链表为空if(NewHead==NULL){NewHead=NewTail=pcur;}else{     //不为空NewTail->next=pcur;//使新链表的尾节点为pcurNewTail=NewTail->next;//使NewTail指向尾节点}}pcur=pcur->next;}if(NewTail)//至关重要的一步{NewTail->next=NULL;//最后尾节点nxet要置为空，否则//新链表最后的元素会粘连原链表}return NewHead;
}

以上几题蕴含着一些巧妙的算法思想，希望对各位有帮助。