顺序表算法题

}注意题目中说的是元素的顺序可以发生改变即不需要保持元素的相对顺序可以进行优化

如果左指针

和上一道题思路大致相同题目说了是非严格递增序列双指针法比较前后两个元素即可

int

{if(nums[src]!nums[dest]){nums[src]nums[dest];}dest;}return

src;

当然可以直接把第二个数组移到第一个数组尾部然后进行排序使用qsort函数

int

三指针法利用两个数组都是非递减排列因为排序好的数组仍然是非递减序列所以我们的两个指针依次从尾部开始向前遍历谁大把谁放到nums1的尾部若从前面开始需要新创建一个数组来存储元素最后再赋值给nums1最后出循环的时候l2和l3只可能有一个小于0

若是l2说明nums2没有遍历完需要将剩下的元素赋值给nums1若是l3则直接返回nums1即可

void

l3n-1;while(l20l30){if(nums1[l2]nums2[l3]){nums1[l1]nums1[l2];l2--;}else{nums1[l1]nums2[l3];l3--;}l1--;}if(l20){while(l10)nums1[l1--]nums2[l3--];}

}链表算法题

在最后需要先判断newtail是否为空**否则链表为空链表时会报错再将其中的next指针置为空否则可能会出现循环**

/***

}在leetcode上给出了递归的方法链表的定义具有递归的性质因此链表题目常可以用递归的方法求解。

这道题要求删除链表中所有节点值等于特定值的节点可以用递归实现。

struct

可以和上一道题一样创建新链表不多赘述这里介绍一种比较巧妙的方法-三指针法

/***

n1,*n2,*n3;n1NULL,n2head,n3head-next;while(n3){n2-nextn1;n1n2;n2n3;n3n3-next;}n2-nextn1;return

head

*fast;slowfasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}return

slow;

和合并数组大致思路相同可以在创建新链表的一开始申请头结点哨兵位避免对于newtail和newhead为空的情况进行讨论

记得最后释放空间

newhead,*newtail;newheadnewtail(ListNode*)malloc(sizeof(ListNode));while(list1list2){if(list1-vallist2-val){newtail-nextlist1;list1list1-next;}else{newtail-nextlist2;list2list2-next;}newtailnewtail-next;}if(list1){newtail-nextlist1;}else{newtail-nextlist2;}ListNode*

retnewhead-next;free(newhead);newheadnewtailNUll;return

ret;

pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针

解题思路创建两个链表分别存放小于x的节点和大于等于x的节点分别进行尾插最后别忘了把大链表的尾节点置为空否则可能会出现死循环还是别忘了释放空间

ListNode*

pHead;while(cur){//小于x的尾插到lessTailif(cur-val

x){lessTail-next

lessTail-next;}//大于等于x的尾插到greaterTailelse{greaterTail-next

cur;greaterTail

cur-next;}//链接两个链表lessTail-next

greaterHead-next;greaterTail-next

NULL;//获取表头pHead

lessHead-next;free(lessHead);free(greaterHead);

return

对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。

给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。

保证链表长度小于等于900

先把链表中的元素值全部保存到数组中然后再判断数组是否为回文。

不建议使用这种解法因为如果没有告诉链表最大长度则不能同此解法

bool

true;}解题思路此题可以先找到中间节点然后把后半部分逆置最近前后两部分一一比对如果节点的值全部相同则即为回文。

快慢指针找中间结点三指针逆置后半部分