题目一:206反转链表
题目要求:
思路分析:两种思路
代码实现:
struct ListNode* reverseList(struct ListNode* head){ //n1,n2反转指针 n3链接下一个结点的指针 struct ListNode* n1,*n2,*n3; n1 = NULL; n2 = head; if(n2)//有可能head本身就是空指针 n3 = n2->next; while(n2)//结束条件:n2==NULL { n2->next = n1; //反转链表 n1 = n2; n2 = n3; if(n3)//坑2:n3到NULL之后要停止,因为不存在NULL->next n3 = n3->next; } return n1; } //第二种写法-->头插 struct ListNode* reverseList(struct ListNode* head){ //设置新的头结点,进行头插 struct ListNode* newhead = NULL; struct ListNode* cur = head; //头插 while(cur) { struct ListNode* next = cur->next; cur->next = newhead; newhead = cur; cur = next; } return newhead; }
题目二:27.移除元素
题目要求:
思路分析:
代码实现:
int removeElement(int* nums, int numsSize, int val){ int src = 0,dest = 0; while(src < numsSize) { //等于val,src++,相当于删除 //不等于val,把src位置的值覆盖到dest位置,src++,dest++ if(nums[src] != val) { nums[dest++]=nums[src++]; // dest++; // src++: } else { src++; } } return dest; }
题目三:删除有序数组中的重复项
题目要求:
思路分析:
代码实现:
int removeDuplicates(int* nums, int numsSize){ int src = 0; int dest = 0; while(src < numsSize) { //相等src++ if(nums[src] == nums[dest]) { src++; } //不等-->将src赋给dest的下一个,src++,dest++ else { nums[++dest] = nums[src++]; } } return dest+1; }
题目四:88.合并两个有序数组
题目要求:
思路分析:
代码实现:
//方法1 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int end1 = m - 1;//nums1末位 int end2 = n - 1;//nums2末位 int end = m + n - 1;//整个数组的末位 while (end1 >= 0 && end2 >= 0)//循环条件:两个都没有结束 { //倒着插入,取大的覆盖 if (nums1[end1] > nums2[end2]) { nums1[end--] = nums1[end1--]; } else { nums1[end--] = nums2[end2--]; } } //nums2有剩余,把剩余元素赋给nums1 while (end2 >= 0) { nums1[end--] = nums2[end2--]; } } //方法2 int cmp_int(const void* ptr1, const void* ptr2) { return (*(int*)ptr1 - *(int*)ptr2); } void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { //第二种方法:存到一起,再利用qsort函数 //直接强行合并两个数组 int i = m; int j = 0; while (j < n) { nums1[i] = nums2[j]; j++; i++; } //利用qsort函数排序 qsort(nums1, m + n, 4, cmp_int); }
总结:
1.一个思路“双指针法”,即利用移动指针(src)和目标指针(dest),来完成对数组元素的操作,大家可以多多画图去理解这个过程;
2.“三指针法”求反转链表,两个指针进行反转,一个指针保证链表的“连接性”