移除元素
题目连接放这了https://leetcode.cn/problems/remove-element/
思路一
创建一个新数组:首先遍历原数组的所有数据,把不等于val的值直接放在新数组里,然后返回新数组的长度。由于这个思路不符合题目的要求,所以我们不采用这个解法,这个思路仅作拓展!!!
int removeElement(int* nums, int numsSize, int val)
{
int n1, n2;
n1 = n2 = 0;
int arr[numsSize];
while (n2 < numsSize)
{
if (nums[n2] != val)
{
arr[n1] = nums[n2];
n1++;
}
n2++;
}
return n1;
}
思路二
使用两个临时变量n1和n2,n2负责遍历数组,n1负责将不等于val的值重新赋值给数组,最后n1就是新数组的下标
这是原数组:
开始进行遍历和赋值操作:
int removeElement(int* nums, int numsSize, int val)
{
int n1, n2;
n1 = n2 = 0;
while(n2 < numsSize)
{
if(nums[n2] != val)
{
nums[n1] = nums[n2];
n1++;
}
n2++;
}
return n1;
}
合并两个有序数组
题目连接放这了https://leetcode.cn/problems/merge-sorted-array/
思路
由于数组nums1有足够的空间,所以我们选择将两个合并的数组就直接放在数组nums1中,现在我们要考虑如何存放,由于两个数组是有序的并且是递增的,存放也是要求递增,所以我们要么从两个数组的首元素开始遍历比较进行存放,要么从两个数组的尾元素开始遍历比较进行存放。
如果从首元素开始遍历存放,比较得到最小的元素,存放在nums1的第一个位置进行存放(因为最后得到的数组元素也要递增排列,所以要从nums1的第一个位置开始存放);这时候就有一个问题了,nums1前面几个原先的元素可能就找不到了,我们举个例子:nums1=[1,2,3,0,0,0],nums2=[0],开始比较,nums2的0小于nums1的1,那nums1的第一个元素1就会被0覆盖掉,导致元素丢失,为了避免这个情况,我们就需要保存这个元素,可是我们不知道要几个变量来保存元素,毕竟nums1有多少的元素比nums2大是不确定的,所以这个方法就比较难实现。
因此我们考虑从尾部开始遍历存放,这时候我们需要三个临时变量,两个变量是分别从两个数组的尾元素进行遍历,剩下一个变量是从nums1最后一个空间开始来进行赋值存放元素的操作。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
int l1, l2, l3;
l1 = m - 1;
l2 = n - 1;
l3 = m + n - 1;
while (l1 >= 0 && l2 >= 0)
{
if (nums1[l1] > nums2[l2])
{
nums1[l3--] = nums1[l1--];
}
else
{
nums1[l3--] = nums2[l2--];
}
}
while (l2 >= 0)
{
nums1[l3--] = nums2[l2--];
}
}
这里稍微解释一下循环遍历条件,首先第一个循环结束条件肯定是两个下标不能小于0,否则会发生数组的越界访问!!!从这个循环条件出来有两种情况,一是l1<0,二是l2<0,为什么不能是两个同时小于0,因为有一个数组会被最先遍历完,然后就会跳出循环,不可能发生两个数组同时遍历完的!!!
跳出循环后,题目要求把nums2合并到nums1中,所以当l2>=0时,说明nums2是没有遍历完的,我们只需要处理这一个条件即可,不用担心nums1了,因为跳出第一个循环后,如果l2>=0,说明nums1数组已经遍历完了,所以不需要考虑nums1了。
移除链表元素
题目连接:https://leetcode.cn/problems/remove-linked-list-elements/
思路一
遍历原链表,将val的节点就地删除。
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
if (head == NULL)
{
return head;
}
ListNode* prev, * pcur;
prev = pcur = head;
ListNode* next;
while (pcur)
{
if (pcur->val == val)
{
next = pcur->next;
prev->next = next;
pcur = next;
}
else
{
prev = pcur;
pcur = pcur->next;
}
}
if (head->val == val)
{
return head->next;
}
return head;
}
这里我们要注意了不用free是因为这时OJ题,如果没有特别说明,我们不需要free,当然你也可以free
还有题目有说可能会出现空链表的情况,这个我们需要单独处理。
在循环中我们是无法删除第一个节点的,所以后面我就用来一个判断来专门处理了一下。
思路二
创建新的链表,将不含val 的节点进行尾插即可。
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
if (head == NULL)
{
return head;
}
ListNode* NewHead, * NewTail;
NewHead = NewTail = (ListNode*)malloc(sizeof(ListNode));
ListNode* ptail = head;
while (ptail)
{
if (ptail->val != val)
{
//尾插
NewTail->next = ptail;
NewTail = NewTail->next;
}
ptail = ptail->next;
}
NewTail->next = NULL;
ListNode* next = NewHead->next;
free(NewHead);
return next;
}
这里隆重介绍一下哨兵位,哨兵位就是头结点,它不存放任何有效的数据,就是一个站岗的功能,有了哨兵位,我们就可以直接进行尾插操作,而不是要单独处理新链表尾空的情况,比较方便,题目要求我们放回第一个有效的节点地址,也很简单,直接放回哨兵位的next就可以了。
然后我们还要注意一下如果原链表为空的时候,我们需要单独处理的。
反转链表
题目连接:https://leetcode.cn/problems/reverse-linked-list/
思路一
创建新链表,使用头插操作就可以实现链表的反转。
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
if (head == NULL)
{
return head;
}
ListNode* NewHead, * NewTail;
NewHead = NewTail = (ListNode*)malloc(sizeof(ListNode));
NewTail->next = NULL;//先置为空,便于最后一个节点指向NULL
ListNode* ptail = head;
ListNode* next;
while (ptail)
{
next = ptail->next;//保存下一个节点
NewTail = NewHead->next;//保存新链表原先的第一个节点
NewHead->next = ptail;//头插
ptail->next = NewTail;//将新的第一个节点和原先的第一个节点进行连接
ptail = next;//继续遍历
}
next = NewHead->next;
free(NewHead);
return next;
}
思路二
原链表进行操作,改变每一个节点的指向,如下图所示:
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
if (head == NULL)
{
return head;
}
ListNode* l1, * l2;
l1 = head;
l2 = head->next;
l1->next = NULL;//先将第一个节点的指向置为NULL
while (l2)
{
ListNode* next = l2->next;//保存下一个节点
l2->next = l1;
l1 = l2;
l2 = next;
}
return l1;
}
合并两个有序的链表
题目链接:https://leetcode.cn/problems/merge-two-sorted-lists/
思路
创建新链表,遍历两个链表的所有的节点,然后尾插到新链表里。
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
ListNode* NewHead, * NewTail;
NewHead = NewTail = (ListNode*)malloc(sizeof(ListNode));
NewHead->next = NULL;//处理空链表的情况
ListNode* l1, * l2;
l1 = list1;
l2 = list2;
while (l1 && l2)
{
if (l1->val < l2->val)
{
NewTail->next = l1;
l1 = l1->next;
NewTail = NewTail->next;
}
else
{
NewTail->next = l2;
l2 = l2->next;
NewTail = NewTail->next;
}
}
if (l1)
{
NewTail->next = l1;
}
if (l2)
{
NewTail->next = l2;
}
ListNode* next = NewHead->next;
free(NewHead);
return next;
}
这里我将哨兵位的next置为NULL,是因为如果两个链表都是空的话,就会放回NULL,也就少写了一些判断语句。
当循环走出去后,一定有一个链表还没有走完,所以直接进行该链表与新链表连接即可,不需要一个节点一个节点的插入,因为剩下的链表本来就是有序的~~
链表的中间节点
题目连接:https://leetcode.cn/problems/middle-of-the-linked-list/
思路
快慢指针,定义两个指针,一个快指针每次走两步,一个慢指针每次走一步,最后快指针遍历完链表的所有节点之后,慢指针就是链表的中间节点
原理就是:2slow = fast
讨论一下循环结束的条件,当有奇数个节点时:
很显然fast->next==NULL时要跳出循环。
当有偶数个节点时:
当fast==NULL时跳出循环。
现在思考是写while(fast->next && fast) 还是写 while(fast && fast->next),还是两个都可以?
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head)
{
ListNode* slow, * fast;
slow = fast = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
公布答案,只能写while(fast && fast->next),两个顺序不能变换,因为如果fast为NULL时,你先写的fast->next会对空指针进行非法访问!!!
环形链表的约瑟夫问题
题目链接:https://www.nowcoder.com/share/jump/9257752291712999799127
思路
这里我们可以使用循环链表来进行操作,循环链表是指头尾节点是相连的:
有了循环链表之后,我们就可以进行删除节点的操作,最后会剩下一个节点,这个节点的next就是它自己,所以循环结束条件就是这个。
用一个计数器来查看是否要进行删除操作,两个指针进行遍历链表,一个保存上一个节点,一个则往前走,一直到循环结束,所以我在创建循环链表这个函数采用放回尾节点,这样便于一开始我们直接拿到头节点和尾节点,方便后续的操作。
typedef struct ListNode ListNode;
ListNode* BuyNewnode(int x)//创建新节点
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->val = x;
newnode->next = NULL;
return newnode;
}
ListNode* CreatList(int n)//创建循环链表
{
ListNode* head, * tail;
head = BuyNewnode(1); //创建第一个节点
tail = head;
for (int i = 2; i <= n; i++)
{
ListNode* newnode = BuyNewnode(i);
tail->next = newnode;
tail = tail->next;
}
tail->next = head;//首尾相连
return tail;
}
int ysf(int n, int m)
{
int count = 1;
ListNode* pcur, * prev;
//创建循环链表
prev = CreatList(n);
pcur = prev->next;
while (prev != prev->next)
{
if (count == m)//删除节点
{
prev->next = pcur->next;
free(pcur);
pcur = prev->next;
count = 1;
}
else
{
prev = pcur;
pcur = pcur->next;
count++;
}
}
int ret = prev->val;
free(prev);
return ret;
}
分割链表
题目链接:https://leetcode.cn/problems/partition-list-lcci/
思路:
我们可以创建两个新链表,一个小链表存放小于x的节点,另一个大链表存放大于或等于x的节点,最后将两个链表合并,放回小链表的头指针即可。
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x)
{
if (head == NULL)
{
return head;
}
ListNode* LessHead, * LessTail;
ListNode* BigHead, * BigTail;
//创建哨兵位
LessHead = LessTail = (ListNode*)malloc(sizeof(ListNode));
BigHead = BigTail = (ListNode*)malloc(sizeof(ListNode));
ListNode* ptail = head;
while (ptail)
{
if (ptail->val < x)
{
LessTail->next = ptail;
LessTail = LessTail->next;
}
else
{
BigTail->next = ptail;
BigTail = BigTail->next;
}
ptail = ptail->next;
}
BigTail->next = NULL;//将大连表的尾节点置为NULL
LessTail->next = BigHead->next;
return LessHead->next;
}
这里要注意你要将大链表的尾节点置为NULL,因为你不确定大链表的尾节点的next是否还指向其他节点!!!
我这里没有删除哨兵位,如果你想删除也可以。
版权声明:本文为博主作者:熵减玩家原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/liwuqianhzc/article/details/137722039