数组和链表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替换dst
while (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;
//1334
int 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 here
ListNode* 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;
else
copy->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;
else
copy->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;
}//这道题对链表的边界有很深的考察