首先直接进入主题,题目链接🔗力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
源代码在最后,有更优解的朋友欢迎在评论里指导我一番!
1.题目分析
通过题目分析得出结论:
1. 将链表分为k个子链表
2. 用一个数组存放这k个子链表,数组的长度就是k
3. 任意两个子链表的长度差不能超过1,也就是要么子链表长度都是2或者别的数字,要么子链表之间可以是2,2,2,1或者3,3,2等。子链表的长度跟链表的长度和k有关。
4. 子链表存放到数组的顺序不能改变,也就是说链表是从头开始分隔的,依次再存放到数组里。
5. 既然数组是存放子链表的,那准确来说数组元素是链表某一节点的地址,之后通过这个节点能找到后面的节点,直到每个子链表的节点到NULL的时候。
我们用图解来展示一下:
我们为了更形象的展现数组里的元素,直接把子链表放入,但我们要知道存放的其实是每个子链表的头节点的地址!
文章来源:https://www.toymoban.com/news/detail-739518.html
知道这样之后,我们直接上代码,代码里有详细介绍!文章来源地址https://www.toymoban.com/news/detail-739518.html
2.源代码
struct ListNode** Create(int k,int* returnSize)
{
*returnSize = k;
struct ListNode** output = (struct ListNode**)malloc(sizeof(struct ListNode*) * k);
if(output == NULL)
{
perror("malloc fail");
exit(-1);
}
//注意!!!!!!1
//这里不初始化会报错的,因为我们这个指针数组存的是指针,必须初始化为空,否则都是野指针
//你想想一个指针数组存放的都是野指针,没有任何意义!
for(int i = 0; i < k; i++)
{
output[i] = NULL;
}
return output;
}
struct ListNode** splitListToParts(struct ListNode* head, int k, int* returnSize)
{
//我们要知道这个题返回的是什么,本题返回的是一个二级指针,也就是存放一级指针的地址,所以在这里开辟的数组
//应该是存放的是链表节点的地址
//我们清楚返回值之后就写题吧
//创建一个指针数组output,用来存放链表节点的地址
struct ListNode** output = Create(k,returnSize);
//链表为空的时候,这个数组都是空指针,因为我们初始化为空了,所以直接返回就可以了。
if(head == NULL)
return output;
//链表不为空的时候
//我们先求链表长度,看分隔的段数是否大于链表长度
struct ListNode* cur = head;
int len = 0;
while(cur)
{
len++;
cur = cur->next;
}
//当链表长度小于要分隔的段数时,很明显链表的节点是不够用的
//当添加完节点之后,剩下的用空指针补齐,我们上面初始化了已经,所以不需要对空指针这里做代码
if(len < k)
{
cur = head;
int i = 0;
while(cur)
{
struct ListNode* next = cur->next;
output[i] = cur;
cur->next = NULL;
cur = next;
i++;
}
}
//当链表长度大于分隔的段数k
//我们这里就要注意一点,任意两部分长度的差距不能超过一
else
{
//这里我们通过n来知道分k段,剩了几个节点
int n = len % k;
//通过m知道,最开始一段分几个节点。
int m = len / k;
int i = 0;
cur = head;
//任意两个部分的长度差距不超过一,那么我们就让第一部分加1,第二部分加1,依次加一,但是加几个呢?
//看n是几,就加几次
while(n--)
{
m = len / k;
output[i] = cur;
while(m)
{
cur = cur->next;
m--;
}
struct ListNode* next = cur->next;
cur->next = NULL;
cur = next;
i++;
}
//在分配完剩余节点个数之后,就正常的一段应该是几个节点
//这里的条件就是下标i小于数组元素个数
while(i < k)
{
m = len / k - 1;
output[i] = cur;
while(m)
{
cur = cur->next;
m--;
}
struct ListNode* next = cur->next;
cur->next = NULL;
cur = next;
i++;
}
}
//最后返回output
return output;
}
到了这里,关于LeetCode刷题之分隔链表(图解➕代码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!