数据结构 ——— 单链表oj题：链表分割（带哨兵位单向不循环链表实现）

目录

题目要求

手搓简易单链表

代码实现 

---

题目要求

现有一链表的头指针 ListNode* head ，给一定值 x ，编写一段代码将所有小于 x 的节点排在其余节点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头节点

举例说明：

输入：x = 5 ; [1,3,9,6,5,4,7,2]

输出：[1,3,4,2,9,6,5,7]

---

手搓简易单链表

代码演示：

struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n1);
struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n2);
struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n3);
struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n4);
struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n5);
struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n6);
struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n7);
struct ListNode* n8 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n8);n1->val = 1;
n2->val = 3;
n3->val = 9;
n4->val = 6;
n5->val = 5;
n6->val = 4;
n7->val = 7;
n8->val = 2;n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n6;
n6->next = n7;
n7->next = n8;
n8->next = NULL;

---

代码实现

代码演示：

struct ListNode* partition(struct ListNode* head, int x)
{// 小于 x 的头尾节点struct ListNode* lesshead;struct ListNode* lesstail;// 大于等于 x 的头尾节点struct ListNode* greaterhead;struct ListNode* greatertail;// 定义哨兵位lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = head;while (cur != NULL){if (cur->val < x){lesstail->next = cur;lesstail = lesstail->next;}else{greatertail->next = cur;greatertail = greatertail->next;}cur = cur->next;}// 链接两个链表lesstail->next = greaterhead->next;greatertail->next = NULL;head = lesshead->next;free(lesshead);free(greaterhead);return head;
}

代码解析：

代码思路：创建两个带哨兵位的单链表，一个用来链接小于 x 的节点，一个用来链接大于等于 x 的节点，最后再把两个链表进行链接，这样就完成了链表的分割，并且没有改变原来的数据顺序

代码逻辑：lesshead 和 lesstail 用来管控小于 x 的节点，lesshead 是哨兵位，不存储有效数据，lesstail 向后链接小于 x 的节点，greaterhead 和 greatertail 作用同上，是用来链接大于等于 x 的节点，进行分割后，不要忘记将 greatertail 的 next 置空，因为分割后 greatertail 节点不一定是为节点，最后再将 lesshead 哨兵位的 next 赋值给 head ，再释放，即可

代码验证：

算法的时间和空间复杂度：

while 循环执行了 N 次，每次内部常数次，只 malloc 开辟了两个节点，可忽略不计

算法的时间复杂度：O(N)

算法的空间复杂度：O(1)