思路一： 创建新的数组，遍历原数组，将不为val的值放到新数组当中。空间复杂度不为O(1)
思路二：双指针法
我们设置两个指针src（源数据）和dst（目标数据）分别指向数组的第一个位置，如果src指向的数值是我们要删除的数据，那么src++，如果src要的数据不是我们要删除的数据，那么把src的数据赋值给dst，并让src++，dst++。
int removeElement(int* nums, int numsSize, int val) { int src,dst; src=dst=0; while(src<numsSize)//numsSize表示数组的长度 { if(nums[src]==val) { src++; } else { nums[dst]==nums[src]; dst++; src++; } return dat;//此时dst的值就是新数组的有效长度 } }
思路一：将num2中数据依次放入到num1数组的后面，用排序算法对num1进行排序
思路二：
l1和l2进行比较。
思路三：
从后往前比大小：比谁大，谁大谁就往后放
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { //nums1Size：nums1数组的长度 //nums2Size：nums2数组的长度 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--]=nums2[l2--]; } else { nums1[l3--]=nums1[l1--]; } } //出了循环有两种情况：l1大于等于0或者l2大于等于0，不存在l1和l2同时大于等于0的情况 //只需要处理一种情况，那就是l2大于等于0，说明l2中的数据还没有完全放入num1中 while(l2>=0) { nums1[l3--]=nums2[l2--]; } //此时nums1中包含了nums2中的数据，num1为升序数组 }
我们需要有一个定义链表的节点的结构，并且将它们连接在一起，就成了链表。
SList.h
typedef int SLDataType; struct SListNode { SLDataType data; struct SListNode*next;//指向下一节点的指针 }SLTNode; void SLTPrint(SLTNode*phead); void SLTPushBack(SLTNode* phead,SLTDataType x); void SLTPushFront(SLTNode* phead,SLTDataType x);
SList.c
void SLTPrint(SLTNode* phead) { SLTNode*pcur=phead; while(pcur) { printf("%d->",pcur->data); pcur=pur->next; } printf("\n"); } //申请新的节点 SLTNode*SLTBuyNode(SLTDataType x) { SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTNode)); if(newnode==NULL) { perror("malloc fail!"); exit(1);//异常退出，正常退出为0 } newnode->data=x; newnode->next=NULL; return newnode; } //尾插 void SLTPushBack(SLTNode**phead,SLTDataType x) { assert(pphead); SLTNode*newnode=SLTBuyNode(x);//在创建 空间之前判断空间是否够用 if(phead==NULL)//处理空链表和非空链表两种情况 { phead=newnode; } else { //找尾 SLNode*ptail=phead; while(ptail->next) { ptail=ptail->next;//ptail指向的就是尾结点 } ptail->next=newnode;//完成了尾插的动作 } } //头插 void SLTPushFront(SLTNode**phaed,SLTDataType x) { assert(pphead); STNode*newnode=SLBuyNode(x); newnode->next=*phead; *pphead=newnode; } //尾删 void SLTPopBack(SLTNode**pphead) { assert(pphead&&*pphead);//链表不能为空 //链表只有一个节点 if((*pphead)->next==NULL)//->优先级高于* { free(*pphead); *pphead=NULL; } else{//链表有多个节点 SLTNode*prev=*pphead; SLTNode*ptail=*pphead; while(ptail->next) { prev=ptail; ptail=ptail->next; } free(ptail); ptail=NULL; prev->next=NULL; } } //头删 void SLPopFront(SLTNode**pphead) { //链表不能为空 assert(pphead&&*pphead);//链表不能为空 SLTNode*next=(*pphead)->next;//->优先级高于* free(*pphead); *pphead=next; } //查找 SLTNode* SLTFind(SLTNode* phead,SLTDataType x) { SLTNode*pcur=phead; while(pcur)//等价于pcur不等于空 { if(pcur->data==x) { return pcur; } pcur=pcur->next; } return pcur; } //在指定位置之前插入数据 void SLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x) { assert(pphead&&*pphead);//如果没有这个数据，就不能插入数据 assert(pos); //在指定位置之前插入数据 //找pos指针的前一个节点 STNode*newnode=SLBuyNode(x); if(pos==*pphead) { SLTPushFront(pphead,x); } else { SLTNode*prev=*pphead;//初始情况下指向第一个节点 while(prev->next!=pos) { prev=prev->next; } // 把prev newnode pos三者连接在一起 newnode->next=pos; pre->next=newnode; } } //在指定位置之后插入数据 void SLTInsertAfter(SLTNode**pphead,SLTNode*pos,SLTDataType x) { assert(pos); STNode*newnode=SLBuyNode(x); newnode->next=pos->next; pos->next=newnode; } //删除pos节点 void SLTErase(SLTNode** pphead,SLTNode*pos) { assert(pphead&&*pphead);//链表不能为空 assert(pos); if(pos==*pphead) { SLTNode* next=(*pphead)->next;//先把头结点的下一个节点储存起来 free(*pphead); *pphead=next;//或者直接采用SLTPopFront(pphead); } else { SLTNode*prev=*pphead; while(prev->next!=pos) { prev=prev->next; } free(pos); pos=NULL; } } //删除pos之后的节点 void SLTEraseAfter(SLTNode* pos) { assert(pos&&pos->next); SLTNode*del=pos->next; pos->next=del->next; free(del); del=NULL; } //销毁链表（销毁一个一个的节点） void SListDestory(SLTNode**pphead) { assert(pphead&&*pphead); SLTNode*pcur=*pphead; while(pcur) { SLTNode*next=pcur->next; free(pcur); pcur=next; } *pphead=NULL; }
如果链表为空，不能对空指针进行解引用，代码会报错。
但是当我们运行之后发现，形参改变了，实参并没有改变。
把头结点释放掉， 再把*pphead走到next指针当中。
当pos=*pphead时，走不通。
上面这两种插入节点的方式是否相同？
1 newnode->next=pos->next; pos->next=newnode;
2 pos->next=newnode; newnode->next=pos->next;
像下面这么操作，是否可行呢？
这样操作就把节点4释放了。我们可以创建一个临时变量del。
test.c
#include"SList.h" void SListTest() { //链表是由一个一个的节点组成 //创建几个节点 SLNode*node1=malloc(sizeof(SLTNode));//对于节点，我们不会涉及到增容的概念，所以我们使用malloc，而不是使用realloc node->data=1; SLNode*node2=malloc(sizeof(SLTNode)); node->data=2; SLNode*node3=malloc(sizeof(SLTNode)); node->data=3; SLNode*node4=malloc(sizeof(SLTNode)); node->data=4;//创建好了4个节点，但是此时这四个节点不能相互找到 //通过每个节点里的next指针，将各个节点连接起来 node1->next=node2; node2->next=node3; node3->next=node4; node4->next=NULL; //调用链表的打印 //再定义一个节点，指向node1，然后作为实参传入 SLTNode*plist=node1; SLTPrint(plist); } int main() { return 0; }
尾插
要找到尾结点，再把尾结点和新节点连接起来。我们让尾结点的下一节点不要指向NULL，而是指向newNode。这样就实现了尾插。
如果我们设置找到ptail的循环条件是while(ptail!=NULL)，那么此时不满足。应该是ptail->next不为空。
