给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

//暴力双循环,只不过时间复杂度不符合
int removeElement(int* nums, int numsSize, int val){int size = numsSize;for(int i = 0; i<numsSize;i++){if(nums[i] == val){for(int j=i+1;j<size;j++){nums[j-1] = nums[j];}i--;size--;}}return size;
}

//快慢指针
int removeElement(int* nums, int numsSize, int val){int left = 0;for(int right = 0; right<numsSize;right++){if(nums[right] != val){nums[left] = nums[right];left++;}}return left;
}

int removeElement(int* nums, int numsSize, int val)
{int src = 0;int dst = 0;while(src < numsSize){if(nums[src] == val){++src;}else{nums[dst] = nums[src];++src;++dst;}}return dst;
}

//k
int removeDuplicates(int* nums, int numsSize){if(numsSize == 0){return 0;}int fast = 1;int slow = 1;while(fast<numsSize){if(nums[fast] != nums[fast-1]){nums[slow++] = nums[fast++];}else{++fast;}}return slow;}

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* addToArrayForm(int* num, int numSize, int k, int* returnSize){//不确定加完的数有多大//考虑到有进位,要多开1位,最多进1位int kSize = 0;int nums = k;while(nums){++kSize;nums /= 10;}int len = kSize > numSize ? kSize+1:numSize+1;int* retArr = (int*)malloc(sizeof(int)*len);//倒着取数组的值并于k的每一位逐个相加int Ai = numSize-1;int ki = 0;int next = 0;//进位int reti = 0;while(Ai >= 0 || ki <kSize){int aVal = 0;if(Ai >= 0){//考虑到数组比K短aVal = num[Ai--];}int kVal = k%10;k /= 10;ki++; int ret = aVal + kVal +next;if(ret >= 10){next = 1;ret -= 10;}else{next = 0;}//正着放不确定从最后一位开始放还是倒数第二位开始放//倒着放到数组,再把数组倒置回来retArr[reti++] = ret;}if(next == 1){retArr[reti++] = 1;//还有一个进位没放要放进去}//逆置int begin = 0;int end = reti - 1;while(begin<end){int tmp = retArr[begin];retArr[begin] = retArr[end];retArr[end] = tmp;begin++;end--;}*returnSize = reti;return retArr;
}

思路一:

题目给的nums1空间大小是m+n,后面的n个位置是空的,就是为了放nums2的元素

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){int p1 = 0;int p2 = 0;int sorted[m+n];while(p1<m || p2<n){if(p1 == m){sorted[p1+p2-1] = nums2[p2++];}else if(p2 == n){sorted[p1+p2-1] = nums1[p1++];}else if(nums1[p1] < nums2[p2]){sorted[p1+p2-1] = nums1[p1++];}else{sorted[p1+p2-1] = nums2[p2++];}}for(int i = 0;i < m+n;i++){nums1[i] = sorted[i];}
}
//额外开辟数组,空间复杂度是O(N)

思路二:大的从后往前放,不需额外开辟数组

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){int end1 = m-1;int end2 = n-1;int end = m+n-1;while(end1>=0 && end2>=0){if(nums1[end1]>nums2[end2]){nums1[end--] = nums1[end1--];}else{nums1[end--] = nums2[end2--];}}//end2结束了,end1还有数据,无需挪动//end1先结束,需要把end2的数据放到nums1里面while(end2>=0){nums1[end--] = nums2[end2--];}
}
//时间复杂度O(m+n) 空间复杂度O(1)

另一种写法

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){int end1 = m-1;int end2 = n-1;int end = m+n-1;while(end1>=0 || end2>=0){if(-1 == end1){//end1为-1说明nums1里面没有元素nums1[end--] = nums2[end2--];}else if(-1 == end2){//nums2没有元素nums1[end--] = nums1[end1--];}else if(nums1[end1]>=nums2[end2]){//谁大谁就放进nums1[end--] = nums1[end1--];}else if(nums1[end1] <= nums2[end2]){nums1[end--] = nums2[end2--];}}
}

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

思路一:两层循环

void rotate(int* nums, int numsSize, int k){int end = numsSize-1;int temp = 0;for(int i=0; i<k; i++){temp = nums[end];for(int j=end; j>0; j--){nums[j] = nums[j-1];}nums[0] = temp;}
}
//时间复杂度O(N*K) 空间复杂度O(1)

思路二:以空间换时间

void rotate(int* nums, int numsSize, int k){int newArr[numsSize];for(int i=0; i<numsSize; i++){newArr[(i+k)%numsSize] = nums[i];}for(int i=0; i<numsSize; i++){nums[i] = newArr[i];}
}
//时间复杂度O(N) 空间复杂度O(N)

思路三 3次逆置

//对原数组后k个数逆置
//对原数组前n-k个数逆置
//对原数组整体逆置
void Reverse(int* arr, int left, int right){while(left<right){int tmp = arr[right];arr[right] = arr[left];arr[left] = tmp;left++;right--;}
}void rotate(int* nums, int numsSize, int k){if(k>numsSize){k %= numsSize;}Reverse(nums, 0, numsSize-k-1);Reverse(nums, numsSize-k, numsSize-1);Reverse(nums, 0, numsSize-1);
}
//空间复杂度O(1),时间复杂度O(N)

考虑清楚多种情况再写代码,

如果第一个值就是val需要单独考虑,prev为NULL的情况

struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* cur = head;struct ListNode* prev = NULL;while(cur != NULL){struct ListNode* next = cur->next;if(cur->val == val){if(prev == NULL){//第一个值就是val的情况free(cur);head = next;cur = next;}   else{prev->next = next;free(cur);cur = next;}}else{prev = cur;cur = cur->next;}}return head;//返回头指针,就不需要传二级指针修改头指针
}

带哨兵位的

struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* guardHead = (struct ListNode*)malloc(sizeof(struct ListNode));guardHead->next = head;struct ListNode* cur = head;struct ListNode* prev = guardHead;while(cur != NULL){if(cur->val == val){struct ListNode* next = cur->next;prev->next = next;free(cur);cur = next;}else{prev = cur;cur = cur->next;}}head = guardHead->next;free(guardHead);guardHead = NULL;return head;
}

思路一: 三指针翻转

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head){if(head == NULL || head->next == NULL){//空链表和只有一个节点的情况return head;}struct ListNode* n1 = NULL;struct ListNode* n2 = head;struct ListNode* n3 = head->next;while(n2 != NULL){//翻转n2->next = n1;//迭代n1 = n2;n2 = n3;if(n3 != NULL){//n2指向最后一个元素时,n3指向的是NULL,不能解引用NULLn3 = n3->next;}}head = n1;return head;
}

思路二:头插法

struct ListNode* reverseList(struct ListNode* head){//包含了空链表和只有一个节点的情况//头插法struct ListNode* cur = head;struct ListNode* newHead = NULL;while(cur != NULL){struct ListNode* next = cur->next;cur->next = newHead;newHead = cur;cur = next;}head = newHead;return head;
}

思路三:递归

在稿纸上画图分析就行,递归核心就是假设后面n-1个已经翻转了

//1->2<-3<-4<-5
//而且第一个要指向NULL
struct ListNode* reverseList(struct ListNode* head){//递归if(head == NULL || head->next == NULL){return head;}struct ListNode* cur = head;struct ListNode* next = cur->next;struct ListNode* newHead = reverseList(next);next->next = cur;cur->next = NULL;return newHead;
}

struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow = head;struct ListNode* fast = head;//快慢指针,快指针一次走2步while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

思路一:暴力循环

struct ListNode* getKthFromEnd(struct ListNode* head, int k){//求链表长度int len = 0;struct ListNode* cur = head;while(cur != NULL){cur = cur->next;len++;}//倒数第k个就是正数第len-k次访问for(int i=0; i<len-k; i++){head = head->next;}return head;
}

思路二:快慢指针

struct ListNode* getKthFromEnd(struct ListNode* head, int k){//快慢指针struct ListNode* slow = head;struct ListNode* fast = head;//fast先走k步while(k--){//考虑空链表以及k>链表长度的问题if(fast == NULL){return NULL;}fast = fast->next;}//快慢同时走while(fast != NULL){fast = fast->next;slow = slow->next;}return slow;
}

牛客的OJ很恶心,很难调
1.自测常规情况,可以过
2.打印一些标记值,不显示输出标记值.比如:段错误
3.思考极端情况场景测试用例(链表为空,k大于链表长度,k为负数等等)

力扣环境很舒服,错了会报测试用例,根据测试用例去改就行

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode* head = NULL;struct ListNode* tail = NULL;if(list1 == NULL && list2 != NULL){return list2;}if(list2 == NULL && list1 != NULL){return list1;}if(list1 == NULL && list2 == NULL){return NULL;}//先取个小的去做头,方便后面尾插if(list1->val < list2->val){head = tail = list1;list1 = list1->next;}else{head = tail = list2;list2 = list2->next;}while(list1 && list2){if(list1->val < list2->val){tail->next = list1;list1 = list1->next;tail = tail->next;}else{tail->next = list2;list2 = list2->next;tail = tail->next;}}//l1或者l2为空就出来了if(list1 == NULL){tail->next = list2;}else if(list2 == NULL){tail->next = list1;}return head;
}

if(list1 == NULL && list2 != NULL){return list2;}if(list2 == NULL && list1 != NULL){return list1;}if(list1 == NULL && list2 == NULL){return NULL;}
//可以写得简洁一点
if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}

思路二:哨兵位

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode* head = NULL;struct ListNode* tail = NULL;//带哨兵位的写法head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));tail->next = NULL;while(list1 && list2){if(list1->val < list2->val){tail->next = list1;list1 = list1->next;tail = tail->next;}else{tail->next = list2;list2 = list2->next;tail = tail->next;}}//l1或者l2为空就出来了if(list1){tail->next = list1;}else if(list2){tail->next = list2;}//开辟的哨兵位用完要释放struct ListNode* node = head;head = head->next;free(node);node = NULL;return head;
}

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。 给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

思路一:开一个int[900]的数组,用数组判断,虽然也能通过牛客的判断,但实际不符合空间复杂度O(1)的要求

思路二: 1.先找到中间节点 2.翻转后半部分链表 3.一一比较

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public://先找到中间节点struct ListNode* midNode(struct ListNode* head){struct ListNode* slow = head;struct ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}//翻转后半部分struct ListNode* ReverseList(struct ListNode* head){//头插法struct ListNode* newHead = NULL;struct ListNode* cur = head;while(cur != NULL){struct ListNode* next = cur->next;cur->next = newHead;newHead = cur;cur = next;}head = newHead;return head;//再一一比较}bool chkPalindrome(ListNode* A) {struct ListNode* mid = midNode(A);struct ListNode* rHead = ReverseList(A);while(A && rHead){if(A->val == rHead->val){A = A->next;rHead = rHead->next;}else{return false;}}return true;}
};

奇数个是怎么过的呢?奇数个理论上不是应该让中间的前一个指向NULL才行吗?

其实是虽然后半部分逆置了,但2还是指向3的,3的next为NULL

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{//考虑空链表if(headA == NULL || headB == NULL){return NULL;}//先算2个链表长度int lenA = 0;int lenB = 0;struct ListNode* curA = headA;struct ListNode* curB = headB;while(curA->next != NULL){curA = curA->next;lenA++;}//各自都少计算一步,相减没影响,这样方便后面判断是否相交while(curB->next != NULL){curB = curB->next;lenB++;}//不相交,此时curA->nxet == NULLif(curA != curB){return NULL;}//注意要把curA curB的位置调整回到一开始curA = headA;curB = headB;//让长的链表先把多出来的长度走了,再一起走if(lenA > lenB){int len = lenA - lenB;while(len--){curA = curA->next;}}if(lenA < lenB){int len = lenB - lenA;while(len--){curB = curB->next;}}//一起走,看谁的指针相同while(curA != curB){curA = curA->next;curB = curB->next;}return curA;
}

另一种写法,长度计算用abs

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{//考虑空链表if(headA == NULL || headB == NULL){return NULL;}//先算2个链表长度int lenA = 0;int lenB = 0;struct ListNode* curA = headA;struct ListNode* curB = headB;while(curA->next != NULL){curA = curA->next;lenA++;}//各自都少计算一步,相减没影响,这样方便后面判断是否相交while(curB->next != NULL){curB = curB->next;lenB++;}//不相交,此时curA->nxet == NULLif(curA != curB){return NULL;}//另一种写法struct ListNode* longList = headA;struct ListNode* shortList = headB;if(lenB > lenA){longList = headB;shortList = headA;}int gap = abs(lenB - lenA);while(gap--){longList = longList->next;}while(longList != shortList){longList = longList->next;shortList = shortList->next;}return longList;
}

不先判断是否相交也行,如果不相交最后返回的也是NULL

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{//考虑空链表if(headA == NULL || headB == NULL){return NULL;}//先算2个链表长度int lenA = 0;int lenB = 0;struct ListNode* curA = headA;struct ListNode* curB = headB;while(curA != NULL){curA = curA->next;lenA++;}//各自都少计算一步,相减没影响,这样方便后面判断是否相交while(curB != NULL){curB = curB->next;lenB++;}//另一种写法struct ListNode* longList = headA;struct ListNode* shortList = headB;if(lenB > lenA){longList = headB;shortList = headA;}int gap = abs(lenB - lenA);while(gap--){longList = longList->next;}while(longList != shortList){longList = longList->next;shortList = shortList->next;}return longList;
}

判断是否为环形链表

//快慢指针
bool hasCycle(struct ListNode *head) {struct ListNode* slow = head;struct ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){return true;}}return false;
}

延申问题:

1. 为什么slow走一步,fast走两步,他们一定会在环内相遇呢,会不会永远追不上?请证明
   不会.假设slow进环的时候,fast跟slow的距离是N,紧接着追击的过程中,slow每走一步,fast走2步,也就是他们自己距离缩减1,迟早会追上
2. slow走一步,fast走3步,4步,x步呢?一定会相遇吗
   不一定.走3步时,他们每走一次,距离缩小2步,如果N是偶数就会相遇,奇数就不会相遇,变成-1时,实际相差C-1,如果C-1也是奇数,那么永远追不上
3. 求环的入口点
   由图推出公式:2(L+X) = L+n * C+X
   L是起点到入口点的距离,X是相遇点到入口点的距离,环的长度是C
   L = n * C-x
   也就是一个指针从head走,一个从meet走,他们会在入口相遇

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow = head;struct ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){//相遇//通过证明,一个指针从head走//一个从meet走,他们会在入口相遇struct ListNode* meet = fast;while(meet != head){meet = meet->next;head = head->next;}return head;}}return NULL;
}

思路二:转换成相交问题

//把环折断,转化为相交问题 注意要翻转链表,且找到入口之后还有翻转回来
struct ListNode* reverseList(struct ListNode* head){//包含了空链表和只有一个节点的情况//头插法struct ListNode* cur = head;struct ListNode* newHead = NULL;while(cur != NULL){struct ListNode* next = cur->next;cur->next = newHead;newHead = cur;cur = next;}head = newHead;return head;
}struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{//考虑空链表if(headA == NULL || headB == NULL){return NULL;}//先算2个链表长度int lenA = 0;int lenB = 0;struct ListNode* curA = headA;struct ListNode* curB = headB;while(curA->next != NULL){curA = curA->next;lenA++;}//各自都少计算一步,相减没影响,这样方便后面判断是否相交while(curB->next != NULL){curB = curB->next;lenB++;}//不相交,此时curA->nxet == NULLif(curA != curB){return NULL;}//另一种写法struct ListNode* longList = headA;struct ListNode* shortList = headB;if(lenB > lenA){longList = headB;shortList = headA;}int gap = abs(lenB - lenA);while(gap--){longList = longList->next;}while(longList != shortList){longList = longList->next;shortList = shortList->next;}return longList;
}struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow = head;struct ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){//相遇//转换成相交问题struct ListNode* meet = fast;struct ListNode* newHead = meet->next;//相交点断开环meet->next = NULL;//需要把head到meet的链表反转struct ListNode* rhead = reverseList(head);struct ListNode* node = getIntersectionNode(newHead,rhead);//再把环恢复原样head = reverseList(rhead);meet->next = newHead;return node;}}return NULL;
}

struct Node* copyRandomList(struct Node* head) {//考虑空链表if(head == NULL){return NULL;}//1.拷贝节点挂到原节点的后面,建立对应关系struct Node* cur = head;while(cur != NULL){struct Node* next = cur->next;struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;cur->next = copy;copy->next = next;cur = next;}//2.处理copy节点的randomcur = head;while(cur != NULL){struct Node* copy = cur->next;if(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}cur = copy->next;}//3.拷贝节点取下来链接到一起,恢复原链表cur = head;//借助哨兵位struct Node* copyHead = NULL;struct Node* copyTail = NULL;copyHead = copyTail = (struct Node*)malloc(sizeof(struct Node));while(cur != NULL){struct Node* copy = cur->next;struct Node* next = copy->next;//尾插copyTail->next = copy;copyTail = copyTail->next;cur->next = next;cur = next;}struct Node* guard = copyHead;copyHead = copyHead->next;free(guard);guard = NULL;return copyHead;
}

struct ListNode* insertionSortList(struct ListNode* head){//空链表或单个节点if(head == NULL || head->next == NULL){return head;}//1.初始条件struct ListNode* sortHead = head;struct ListNode* cur = head->next;sortHead->next = NULL;while(cur)//2.终止条件{//3.迭代条件struct ListNode* next = cur->next;//将cur节点插入到前面有序区间struct ListNode* p = NULL;struct ListNode* c = sortHead;while(c){if(cur->val < c->val){break;}else{p = c;c = c->next;}}if(p == NULL)//头插{cur->next = c;sortHead = cur;}else//插中间和尾插{p->next = cur;cur->next = c;}cur = next;}return sortHead;
}

自己考虑好极端情况,空链表,单节点,元素都相同

struct ListNode* deleteDuplication(struct ListNode* pHead ) {//空链表或一个节点if(pHead == NULL || pHead->next == NULL){return pHead;}//1.起始条件struct ListNode* prev = NULL;struct ListNode* cur = pHead;struct ListNode* next = pHead->next;while(next){if(cur->val == next->val){//删除重复的//让next往前走,直到碰到不相等的//如果最后几个元素都相等,那么next有可能走到空while(next && next->val == cur->val){next = next->next;}if(prev == NULL){pHead = next;cur = next;if(next != NULL){next = next->next;}}if(prev != NULL){cur = next;prev->next = next;if(next != NULL){next = next->next;}}}else{prev = cur;cur = next;if(next != NULL){next = next->next;}}}return pHead;
}

另一种写法:三指针

struct ListNode* deleteDuplication(struct ListNode* pHead ) {//空链表或一个节点if(pHead == NULL || pHead->next == NULL){return pHead;}//1.起始条件struct ListNode* prev = NULL;struct ListNode* cur = pHead;struct ListNode* next = pHead->next;while(next){if(cur->val == next->val){//删除重复的//让next往前走,直到碰到不相等的//如果最后几个元素都相等,那么next有可能走到空while(next && next->val == cur->val){next = next->next;}//删除cur到next之间的节点while(cur != next){struct ListNode* del = cur;cur = cur->next;free(del);del = NULL;}//考虑是否需要改变pHeadif(prev == NULL){pHead = cur;}else{prev->next = cur;}if(next != NULL){next = next->next;}}else{prev = cur;cur = next;next = next->next;}}return pHead;
}