💖💖💖欢迎来到我的博客，我是anmory💖💖💖
又和大家见面了
欢迎来到动画详解LeetCode系列
用通俗易懂的动画的动画使leetcode算法题可视化
先来自我推荐一波
个人网站欢迎访问以及捐款
推荐阅读
如何低成本搭建个人网站
专栏:动画详解leetcode算法题
C语言知识

---

题目描述

---

解题思路

本题可以通过两个链表来解决
一个链表是小链表，用来存储比x小的元素
一个链表是大链表，用来存储大于等于x的元素
最后再将大小链表首尾相接就可以了

---

动画详解

---

代码实现

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;struct ListNode* partition(struct ListNode* head, int x)
{ListNode* lessHead, *lessTail;ListNode* greatHead,*greatTail;lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));greatHead = greatTail = (ListNode*)malloc(sizeof(ListNode));ListNode* pcur = head;while(pcur){if(pcur->val<x){// 插入到小链表中lessTail->next = pcur;// 这里的思想可以学习一下lessTail = lessTail->next;}else{// 插入到大链表中greatTail->next = pcur;greatTail = greatTail->next;}pcur = pcur->next;}// 把大链表的尾部置空，防止出现链表循环greatTail->next = NULL;// 大小链表首尾相接lessTail->next = greatHead->next;return lessHead->next;
}

---

注意事项

在这个代码中，如果不将greatHead->next置空的话，会导致死循环
因为最后一个greatHead->next会指向pcur中的一个元素，从而形成一个闭环导致运行超时

---

复杂度分析

本代码中仅有一个while循环，时间复杂度为O(n)

---

总结

💖💖💖非常感谢各位的支持💖💖💖
我们共同进步
本系列持续更新，关注我，带你手撕面试算法题
下期再见