数组和链表OJ题

leetcode用编译器调试的技巧

数组和链表练习题

leetcode/reverse_Link/main.c · Hera_Yc/bit_C_学习 - 码云 - 开源中国

1、移除元素

27. 移除元素 - 力扣（LeetCode）

int removeElement(int* nums, int numsSize, int val)
{int src = 0, dst = 0;//用src替换dstwhile (src < numsSize){if (nums[src] != val){nums[dst] = nums[src];src++;dst++;}else{++src;}}return dst;
}

2、删除排序数组中的重复项

26. 删除有序数组中的重复项 - 力扣（LeetCode）

int removeDuplicates(int* nums, int numsSize) 
{int prev = 0;int cur = prev+1;int dst = 0;while (cur < numsSize){if (nums[prev] == nums[cur]){prev++;cur++;}else{nums[dst] = nums[prev];dst++;prev++;cur++;}}nums[dst] = nums[prev];dst++;return dst;}

3、数组形式的加法

989. 数组形式的整数加法 - 力扣（LeetCode）

//数组形式的加法
//大数的加法
int* addToArrayForm(int* num, int numSize, int k,int* returnSize)
{int KSize = 0;//求出K的位数int Num = k;while (Num){Num /= 10;KSize++;}//比较K的位数和数组的长度谁大?最终结果的位数:一定是大的那位+1(或者就是最大的那一位)//保险起见:我们用大一位开辟内存//calloc初始化一下int* retArr = (int*)calloc((KSize > numSize ? KSize + 1 : numSize + 1),sizeof(int));int tmp = 0;int cur = numSize - 1;int flag = 0;//进位//对于retArr可以倒着放,也可以正着放,然后逆置int reti = 0;int len = KSize > numSize ? KSize : numSize;while (len--){int tmpn = 0;if (cur >= 0){tmpn = num[cur];}tmp = k % 10;k = k / 10;retArr[reti] = tmp + tmpn + flag;//完成每一位的计算if (retArr[reti] >= 10){retArr[reti] = retArr[reti] - 10;flag = 1;//如果进位了}else{flag = 0;}cur--;reti++;}//观察进位符号是否为1:if (flag == 1){retArr[reti] = 1;//首位reti++;}//逆置int left = 0;int right = reti - 1;while (left < right){int tmp = retArr[left];retArr[left] = retArr[right];retArr[right] = tmp;left++;right--;}*returnSize = reti;return retArr;
}int main()
{int arr[4] = { 3,4 };int k = 1200;//1334int size = 0;int* p = NULL;p=addToArrayForm(arr, 2, k,&size);int i = 0;for (i = 0; i < 4; i++){printf("%d ", p[i]);}
}

4、反转链表

反转链表（逆置单链表），可以说是链表最关键的操作之一。(两种方法)。

206. 反转链表 - 力扣（LeetCode）

 //三指针逆方向
struct ListNode* reverseList(struct ListNode* head) 
{if(head==NULL||head->next==NULL){return head;}else{struct ListNode* cur=head;struct ListNode* prev=NULL;while(cur!=NULL){struct ListNode* tmp=cur->next;cur->next=prev;prev=cur;cur=tmp;}return prev;}
}//头插法
//头插创建新链表
//取cur头插到以newhead为头的新链表中
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* newhead = NULL; //新链表的头结点struct ListNode* cur = head;struct ListNode* next = NULL;while (cur != NULL){next = cur->next;   //保存cur的下一个结点cur->next = newhead;  //头插:把cur看作待插入的新结点newhead = cur;cur = next;}return newhead;
}//头插更容易理解

5、删除所有给定值的结点

203. 移除链表元素 - 力扣（LeetCode）

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

6、链表的中间结点

链表中的双指针问题：快慢指针。

对于一个单链表来说：

快指针每次走两步。
慢指针每次走一步。
当快指针走到尾时，慢指针恰好在链表的中间。

这里对结点个数不同的链表，快指针有所差异（所指向的尾的不同）。

876. 链表的中间结点 - 力扣（LeetCode）

struct ListNode* middleNode(struct ListNode* head) {if (head->next == NULL) {return head;} else {struct ListNode* cur = head;int count = 0;while (cur != NULL) {count++;cur = cur->next;}count = count / 2;cur = head;while (count) {cur = cur->next;count--;}return cur;}
}//追加：要求只能遍历链表一次
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow = head;struct ListNode* fast = head;while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;}return slow;
}

7、输入一个链表，输出该链表中倒数第k个结点（双指针变形）。

struct ListNode* func(struct ListNode* head, int k){struct ListNode* slow = head;struct ListNode* fast = head;while (k--&&fast){    //k有可能大于链表的长度fast = fast->next;}if (fast == NULL) return NULL;while (fast){slow = slow->next;fast = fast->next;}return slow;}

8、合并有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{// 取小节点下来尾插if (list1 == NULL && list2 == NULL)return NULL;if (list1 == NULL)return list2;if (list2 == NULL)return list1;struct ListNode* head = NULL;struct ListNode* tail = 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;}else {tail->next = list2;list2 = list2->next;}tail = tail->next;}if (list1 == NULL){tail->next = list2;}if (list2 == NULL){tail->next = list1;}return head;}//方法二：哨兵位
struct ListNode* mergeTwoLists2(struct ListNode* list1, struct ListNode* list2) {//带头结点的链表（哨兵位）if (list1 == NULL && list2 == NULL)return NULL;if (list1 == NULL)return list2;if (list2 == NULL)return list1;struct ListNode* head = NULL;struct ListNode* tail = NULL;//带哨兵位的头结点，不存储有效数据，主要是方便尾插head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));//取小的尾插 while (list1 && list2){if (list1->val < list2->val){tail->next = list1;list1 = list1->next;}else {tail->next = list2;list2 = list2->next;}tail = tail->next;}if (list1 == NULL){tail->next = list2;}if (list2 == NULL){tail->next = list1;}struct ListNode* realhead = head->next;free(head);head = NULL;return realhead;
}

哨兵位：head = tail = (struct ListNode*)malloc(sizeof(struct ListNode))，这里的head就是哨兵，不存储任何数据，只是在尾插时不需要对list进行判断。哨兵位对尾插来说更加方便，但在绝大多数的oj题中，链表一般是不带哨兵位的，第一个头结点存储的有数据。

9、链表分割

链表分割_牛客题霸_牛客网（双哨兵位尾插链表）

这里的maxtail不置空会产生环.

struct ListNode* partition(struct ListNode* phead, int x)
{// write code here//把pHead的结点拿出来,分两个尾插://可以尾插,亦可以头插然后反转//小于x插一次,大于x的插一次//最后整合两个链表,释放哨兵//1.空链表//if(phead==NULL)return NULL;//2.只有一个结点//if(phead->next==NULL)return phead;//1和2合并if (phead == NULL || phead->next == NULL)return phead;//3.有1个以上的结点//开辟两个哨兵struct ListNode* minhead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* maxhead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = phead;struct ListNode* mintail = minhead;struct ListNode* maxtail = maxhead;//初始化:防止内存错误minhead->next = NULL;maxhead->next = NULL;while (cur){/*链表在这里构成环了,导致的死循环*/if (cur->val < x){mintail->next = cur;mintail = mintail->next;}else{maxtail->next = cur;maxtail = maxtail->next;}cur = cur->next;}mintail->next = maxhead->next;maxtail->next = NULL;//防止环的生成struct ListNode* realhead = minhead->next;free(minhead);minhead = NULL;free(maxhead);maxhead = NULL;return realhead;
}

10、回文链表

链表的回文结构_牛客题霸_牛客网（回文链表=链表逆置+链表的中间结点）

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* newhead = NULL;  //新链表的头结点struct ListNode* cur = head;struct ListNode* next = NULL;while (cur != NULL) {next = cur->next;   //保存cur的下一个结点cur->next = newhead;  //头插:把cur看作待插入的新结点newhead = cur;cur = next;}return newhead;}//头插更容易理解bool chkPalindrome(ListNode* A) {// write code hereListNode* fast = A;ListNode* slow = A;ListNode* prev = NULL;while (fast && fast->next) {prev = slow;slow = slow->next;fast = fast->next->next;}//利用快慢指针找到那个中间结点prev->next = NULL;//分割前后两个链表slow = reverseList(slow);//反转后一半链表//逐一比较while (A) {if (A->val != slow->val) {return false;} else {A = A->next;slow = slow->next;}}return true;
}

11、相交链表的公共节点

160. 相交链表 - 力扣（LeetCode）

#include <math.h>struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB) {// 用相交结点的地址去比// 不能用结点的值去比,因为不同的结点可以存相同的值struct ListNode* curA = headA;struct ListNode* curB = headB;//这里用第二种思路:用两个链表的差值int la = 0;int lb = 0;while (curA) {la++;curA = curA->next;}//求链表A的长度while (curB) {lb++;curB = curB->next;}//求链表B的长度struct ListNode* longList = headA;struct ListNode* shortList = headB;if (lb > la) {longList = headB;shortList = headA;}int gap = abs(la - lb);//求两链表的长度差while (gap--) {        //让长的链表先走gap步longList = longList->next;}//这步操作的结果使:longList和shortList距离链表的末尾一样近while (longList) {if (longList == shortList)//比较的只能是地址,不能是值,即使两个结点值相同,也有可能不是同一个结点return longList;longList = longList->next;shortList = shortList->next;}return NULL;}

12、环形链表 i

141. 环形链表 - 力扣（LeetCode）（快慢指针）

bool hasCycle(struct ListNode *head) {struct ListNode* slow=head;struct ListNode* fast=head;while(fast&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;if(fast==slow){return true;}}return false;
}

13、环形链表ii

142. 环形链表 II - 力扣（LeetCode）

这里有个很难理解的方法：待补充……

14、复杂链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

struct Node* copyRandomList(struct Node* head)
{if (head == NULL)return NULL;struct Node* cur = head;//1.将拷贝结点链接在原结点的后面while (cur){//构造拷贝结点struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->next = NULL;copy->random = NULL;copy->val = cur->val;copy->next = cur->next;cur->next = copy;cur = copy->next;}//2.处理拷贝结点的随机指针random/**这里有个较难理解的点：* 1.对于拷贝结copy点来说:它的random指针指向的必须是拷贝结点.* 2.对于原结点cur来说:它的random指针指向的是原结点* 3.cur->random:是cur随机指针指向的原结点* 4.对于任何一个原结点来说:它后面的结点就是自己的拷贝结点* 因此:* 5. copy->random = cur->random->next*/cur = head;while (cur){struct Node* copy = cur->next;if (cur->random != NULL)copy->random = cur->random->next;elsecopy->random = NULL;cur = copy->next;}//3.拆解出拷贝链表cur = head;struct Node* copyHead = head->next;while (cur){struct Node* copy = cur->next;struct Node* next = copy->next;cur->next = next;if (next != NULL)copy->next = next->next;elsecopy->next = NULL;cur = next;}return copyHead;
}
//leetcode这道题的C底层有错误，不能通过，只能用C++来实现

15、对链表进行插入排序

147. 对链表进行插入排序 - 力扣（LeetCode）(需要画图详解)

struct ListNode* insertionSortList(struct ListNode* head) {// struct ListNode* phead=(struct ListNode*)malloc(sizeof(struct ListNode));if (head == NULL || head->next == NULL)return head;struct ListNode* sorthead = head;struct ListNode* cur = head->next;sorthead->next = NULL;// sorthead做头结点,不断取结点插入sorthead中,不断头插/尾插/中间插入while (cur) {struct ListNode* next = cur->next;// 把cur插入到sorthead中，并且保持链表有序if (cur->val <= sorthead->val) {// 头插cur->next = sorthead;sorthead = cur;} else {// 中间或尾插struct ListNode* sortprev = sorthead;struct ListNode* sortcur = sortprev->next;while (sortcur) {if (sortcur->val >= cur->val) {sortprev->next = cur;cur->next = sortcur;break;} else {sortprev = sortcur;sortcur = sortcur->next;}}if (sortcur == NULL) {sortprev->next = cur;cur->next = NULL;}}cur = next;}return sorthead;
}
//取结点往sorthead插入

16、删除链表重读元素

82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

struct ListNode* deleteDuplicates(struct ListNode* head) {if (head == NULL || head->next == NULL)return head;struct ListNode* prev = NULL;struct ListNode* cur = head;struct ListNode* next = cur->next;while (next) {if (cur->val != next->val) {prev = cur;cur = next;next = next->next;} else {while (next != NULL && cur->val == next->val) {next = next->next;}// 不free掉这些结点也不会报错if (prev != NULL) {prev->next = next;} else {head = next;}// 释放while (cur != next) {struct ListNode* del = cur;cur = cur->next;free(del);}if (next != NULL)next = next->next;}}return head;
}//这道题对链表的边界有很深的考察