C语言题目练习4
这一篇博客我们继续在算法题的世界里面遨游~
链表分割
链表分割：
https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70
这是一道来自牛客网上面的题目，我们需要将一个链表分割，同时不可以改变原来的顺序，这里提供一种思路~
思路
创建两个链表，一个 小链表保存比 x 小的结点，另外一个 大链表保存剩余的结点，再将 大链表和小链表首尾相连，得到我们想要的链表。（结合前面让代码更简单，我们可以向操作系统借空间创建链表，这样就不需要判断是否为空）
代码实现：
class Partition
{
public:
ListNode* partition(ListNode* pHead, int x)
{
//创建小链表
ListNode* lessHead, * lessTail;
//减少代码量，减少判断是否为空操作
lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));
//创建大链表
ListNode* greaterHead, * greaterTail;
greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));
//遍历原来的链表
ListNode* pcur = pHead;
while (pcur)
{
//结点比x小放入小链表(尾插）
if (pcur -> val < x)
{
lessTail->next = pcur;
lessTail = pcur;
}
//结点比x大放入大链表（尾插）
else
{
greaterTail->next = pcur;
greaterTail = pcur;
}
//继续遍历
pcur = pcur->next;
}
//首尾相连
lessTail->next = greaterHead->next;
//大链表尾结点下一个结点置为空，避免死循环
greaterTail->next = NULL;
//保存返回的结点
ListNode* reNode = lessHead->next;
//释放动态申请的空间（一块空间释放一次就可以了）
free(lessHead);
lessHead = NULL;
free(greaterHead);
greaterHead = NULL;
//返回结点
return reNode;
}
}
我们的代码运行成功~
原文地址：https://blog.csdn.net/2401_82924480/article/details/142922245
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！