【数据结构】--单链表力扣面试题⑤链表分割

一、有相对顺序的链表分割

二、无相对顺序的链表分割

一、有相对顺序的链表分割

题述：现有一链表的头指针ListNode* phead,给一定值x,编写一段代码将所有<x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排序后的链表的头指针。

示例如下：

思路：难就难在不能改变相对顺序。那我们的思路是创建两个链表，一个链表尾插<x的值，一个链表尾插>x的值，然后再把两个链表顺序链接即可。并且我们还会给两个链表定义尾指针，lessTail和greaterTail，并且会开辟一个头结点，这两个操作都是为了方便尾插。没有头结点还要多加一个判断。

但是如果开辟头结点，还要多两个操作：

1、我们题中默认都是没有头结点的，如果要返回头指针，他一定是要返回头结点的下一节点的地址，并且在两个链表链接过程中，一定是链接后面的头结点后的那一个节点。

2、要释放节点的内存，要返还给操作系统。

小知识：一般上oj上是不会限制空间复杂度的，如果出现报错，内存限制：您的程序使用了超出限制的内存。这种问题可能是由死循环等的问题造成的。

#include<stdio.h>
#include<stdlib.h>struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* partition(struct ListNode* phead, int x)
{struct ListNode* lessHead, * lessTail, * greaterHead, * greaterTail;lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));//开辟一个头结点,使头指针和尾指针都指向头结点，以便遍历链表greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = phead;//用cur来遍历原链表while (cur)//结束条件一定是遍历完原链表{if (cur->val < x){lessTail->next = cur;lessTail = cur;}else{greaterTail->next = cur;greaterTail = cur;}cur = cur->next;//无论如何,链接完一个结点后都要往下走一次}lessTail->next = greaterHead->next;//将>=x的链表链接在<x的链表后面。//这里是=greaterHead->next的原因是greaterHead是头结点，是你自己开辟的，题里面不要这个！greaterTail->next = NULL;//使>=x的链表最后指向是NULL,防止构成环形链表struct ListNode* newnode = lessHead->next;//因为lessHead是头结点，我们不要！free(lessHead);//因为lessHead始终指向头结点，所以直接释放free(greaterHead);return newnode;
}
int main()
{struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));int k = 5;n1->val = 1;n2->val = 2;n3->val = 4;n4->val = 3;n5->val = 9;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = NULL;struct ListNode* obj = partition(n1, k);while (obj){printf("%d", obj->val);obj = obj->next;}return 0;
}

运行代码如下：

如果不要求相对顺序呢？

二、无相对顺序的链表分割

示例：

思路：给一个头head和一个尾tail,<x值的头插，>=x值的尾插即可实现。毕竟不要求相对顺序。只要求<x的节点在前面，>=x的节点在后面即可。

并且既要头插又要尾插的话就不建议创建一个头结点了，因为夹在中间，他还没用，会造成妨碍。

#include<stdio.h>
#include<stdlib.h>struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* partition(struct ListNode* phead, int x)
{struct ListNode* head = NULL, * tail = NULL;struct ListNode* cur = phead,* prev = NULL;while (cur){if (cur->val < x){//头插要判断，如果是在中间头插，先要保存cur的下一个节点的地址才行if (head == NULL){head = tail = cur;cur = cur->next;}else{prev = cur->next;cur->next = head;head = cur;cur = prev;}}else{//尾插就不需要考虑太多了if (head == NULL){head = tail = cur;}else{tail->next = cur;tail = cur;}cur = cur->next;}}return head;
}
int main()
{struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));int k = 5;n1->val = 1;n2->val = 2;n3->val = 4;n4->val = 3;n5->val = 9;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = NULL;struct ListNode* obj = partition(n1, k);while (obj){printf("%d", obj->val);obj = obj->next;}return 0;
}