725. 分隔链表
判断可能存在的情况：
1.链表恰好能被完整分割成k份；
2.链表无法被分割成k份；
3.链表可以被分割成k份，但仍有剩余节点；
思路：
首先求出链表的总长度，判断能否被完整分割成k份；如果链表可以被分割成k份，但仍有剩余，那么前面的几个链表每个就得多得一个节点；如果无法被分割成k份，那么我们就得将每个节点分成单个链表，然后再将无法被分割出来的链表置为NULL；
int GetListLen(struct ListNode* head)
{
struct ListNode* cur = head;
int len = 0;
while(cur)
{
len++;
cur = cur->next;
}
return len;
}
struct ListNode** splitListToParts(struct ListNode* head, int k, int* returnSize)
{
struct ListNode** lists = (struct ListNode**)malloc(sizeof(struct ListNode*) * k);
*returnSize = k;
//获取链表长度
int list_len = GetListLen(head);
//剩余节点
int remain_node = list_len % k;
//遍历链表
struct ListNode* cur = head, *new_head = head;
int i = 0;
int ans = k;
int flag = 1;
//无法被分割成k份，那么就得将修改分割次数
if(list_len < k)
{
ans = list_len;
}
while(ans--)
{
//平均下来每个链表的长度
int ListLen = list_len / k;
//将剩余节点一一分配给前面的链表
if(remain_node)
{
ListLen = list_len / k + 1;
remain_node--;
}
//遍历链表，到达要断开的位置
while(--ListLen)
{
cur = cur->next;
}
//将链表断开，添加入结果
struct ListNode* next = cur->next;
cur->next = NULL;
lists[i] = new_head;
//刷新下一个链表的起点
cur = next;
new_head = next;
i++;
}
//将无法分割出来的链表置为NULL
for(int j = i; j < k; j++)
{
lists[j] = NULL;
}
return lists;
}
1670. 设计前中后队列
思路：
这道题的难点主要在于对中间节点的增删，题目提到如果有两个中间节点，那么我们要去前面的节点进行操作，也就是说：在插入后，节点数如果为奇数，该节点应该正好在中间；如果插入后节点数为偶数，该节点为两个中间节点的较前一个； 删除也是同理：在删除时，如果节点数为奇数，我们就删除正中间的那个；如果为偶数，我们就删除两个节点的较前一个；
我们设计一个函数，来获取中间节点的前一个节点指针：
//找到中间节点的前一个节点
Node* GetMidPrevNode(FrontMiddleBackQueue* obj)
{
Node* slow = obj->head, *fast = obj->head, *prev = NULL;
while(fast && fast->next)
{
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
return prev;
}
当删除中间节点时，如果节点数为偶数，这个函数将会向我们提供两个中间节点的较前一个节点；如果节点数为奇数，它会提供给我们正中间节点的前一个结点的指针；所以我们需要根据节点数来判断要删除的中间节点究竟是哪一个。
注意：我们在插入时需要对节点数为1时的队列进行特殊判断，因为中间节点此时应该插在队列的头部，这会改变头节点的指向；在删除时，需要对节点数小于等于2的队列进行特殊判断，因为此时中间节点都为头节点，删除它也会改变头节点的指向；
typedef struct Node
{
struct Node* next;
int val;
}Node;
typedef struct
{
Node* head;//头部
Node* tail;//尾部
int size;//记录当前元素个数
} FrontMiddleBackQueue;
//创建新节点
Node* CreateNewNode(int val)
{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->next = NULL;
new_node->val = val;
return new_node;
}
//判空
bool QueueEmpty(FrontMiddleBackQueue* obj)
{
return obj->size == 0;
}
//找到中间节点的前一个节点
Node* GetMidPrevNode(FrontMiddleBackQueue* obj)
{
Node* slow = obj->head, *fast = obj->head, *prev = NULL;
while(fast && fast->next)
{
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
return prev;
}
//找到要删除的中间节点的前一个
Node* FindNodePrev(FrontMiddleBackQueue* obj, Node* mid)
{
Node* cur = obj->head;
while(cur && cur->next != mid)
{
cur = cur->next;
}
return cur;
}
FrontMiddleBackQueue* frontMiddleBackQueueCreate()
{
FrontMiddleBackQueue* obj = (FrontMiddleBackQueue*)malloc(sizeof(FrontMiddleBackQueue));
obj->head = obj->tail = NULL;
obj->size = 0;
return obj;
}
void frontMiddleBackQueuePushFront(FrontMiddleBackQueue* obj, int val)
{
//创建新节点
Node* new_node = CreateNewNode(val);
//如果队列为空
if(QueueEmpty(obj))
{
//头尾指向同一元素
obj->head = obj->tail = new_node;
}
else
{
new_node->next = obj->head;
obj->head = new_node;
}
obj->size++;
}
void frontMiddleBackQueuePushMiddle(FrontMiddleBackQueue* obj, int val)
{
Node* mid_prev = GetMidPrevNode(obj);
Node* new_node = CreateNewNode(val);
//选择在中间节点的右边进行插入，确保：
//1.当有两个中间位置时，其能在较前面
//2.当只有一个中间节点时，其在正中间
//队列为空
if(QueueEmpty(obj))
obj->head = obj->tail = new_node;
//当只有一个节点时，采用头插
else if(obj->size == 1)
{
frontMiddleBackQueuePushFront(obj,val);
return;
}
//当有两个及以上节点
else
{
new_node->next = mid_prev->next;
mid_prev->next = new_node;
}
obj->size++;
}
void frontMiddleBackQueuePushBack(FrontMiddleBackQueue* obj, int val)
{
Node* new_node = CreateNewNode(val);
//如果队列为空
if(QueueEmpty(obj))
obj->head = obj->tail = new_node;
//有一个及以上节点
else
{
obj->tail->next = new_node;
obj->tail = new_node;
}
obj->size++;
}
int frontMiddleBackQueuePopFront(FrontMiddleBackQueue* obj)
{
//队列为空
if(QueueEmpty(obj))
return -1;
int tmp = obj->head->val;
//只有一个节点
if(obj->size == 1)
{
free(obj->head);
obj->head = obj->tail = NULL;
}
//两个及以上节点
else
{
Node* new_head = obj->head->next;
free(obj->head);
obj->head = new_head;
}
obj->size--;
return tmp;
}
int frontMiddleBackQueuePopMiddle(FrontMiddleBackQueue* obj)
{
if(QueueEmpty(obj))
return -1;
//该函数如果在偶数个情况下，返回两个中间位置的较前一个
//在奇数情况下，返回中间节点的前一个
Node* mid = GetMidNode(obj);
int tmp = 0;
//如果只有一个或两个节点,调用头删
//当只有一个或两个节点时，中间节点为首节点
if(obj->size == 1 || obj->size == 2)
{
return frontMiddleBackQueuePopFront(obj);
}
else
{
if(obj->size % 2 == 1)
mid = mid->next;
tmp = mid->val;
//找到要删除的节点的前一个
Node* prev = FindNodePrev(obj,mid);
prev->next = mid->next;
free(mid);
}
obj->size--;
return tmp;
}
int frontMiddleBackQueuePopBack(FrontMiddleBackQueue* obj)
{
if(QueueEmpty(obj))
return -1;
int tmp = obj->tail->val;
if(obj->size == 1)
obj->head = obj->tail = NULL;
else
{
Node* prev = FindNodePrev(obj,obj->tail);
prev->next = NULL;
free(obj->tail);
obj->tail = prev;
}
obj->size--;
return tmp;
}
void frontMiddleBackQueueFree(FrontMiddleBackQueue* obj)
{
Node* cur = obj->head;
while(cur)
{
Node* next = cur->next;
free(cur);
cur = next;
}
}