目录
1. 题目描述及链接
2. 解题思路
2.1 思路1
2.2 思路2
2.3 思路3（本题采取该解法）
3. 题解程序
1. 题目描述及链接
题目链接：面试题 02.04. 分割链表 - 力扣（LeetCode）
题目描述：
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
2. 解题思路
2.1 思路1
创建结构体指针变量curNode遍历原链表：
当curNode的val值大于给定的X时，将该结点尾插后释放该结点；
当curNode的val值小于给定的X时，保持该结点不动，再检查下一结点；
2.2 思路2
重新创建一个新链表，并为其设置一个哨兵位。
创建指针变量curNode遍历原链表，当curNode的val值大于给定的X时，进行尾插操作；
当curNode的val值小于给定的X时，进行头插操作。
2.3 思路3（本题采取该解法）
总思路：
创建指针变量curNode遍历原链表，当curNode的val值小于给定的X时，尾插到小链表；
当curNode的val值大于给定的X时，尾插到大链表；
具体思路：
（1）为实现大小链表的正确尾插，需要创建对应指针变量指向当前的尾结点，并在插入后更新尾结点。分别命名为greaterTail和lessTail；
（2）同时，新建链表为空时，空指针->next会导致空指针解引用。故而新链表为空需单独讨论，较为麻烦。此处采用设置哨兵位，分别记为greaterHead和greaterTail：
（3）由于创建了头结点（哨兵位），最后需手动释放；
（4）注意由于哨兵位并不存放实际有效的值，故大链表链接到小链表尾部时，实际链接的大链表第一个结点是greaterHead->next；最后返回新链表的第一个结点是lessHead->next；
（5）考虑特殊情况，若原链表为空，则大小链表仅有哨兵位，即greaterHead->next为NULL，lessTail->next也为NULL，直接返回NULL即可。
3. 题解程序
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {if(head==NULL){return NULL;}// 创建两个带头链表ListNode* lessHead,*lessTail;ListNode* greaterHead,*greaterTail;lessHead=lessTail=(ListNode*)malloc(sizeof(ListNode));greaterHead=greaterTail=(ListNode*)malloc(sizeof(ListNode));// 遍历原链表，将结点分别尾插到大小链表ListNode* curNode=head;while(curNode!=NULL){if(curNode->val < x){// 尾插到小链表中lessTail->next=curNode;lessTail=lessTail->next;}else{// 尾插到大链表中greaterTail->next=curNode;greaterTail=greaterTail->next;}curNode=curNode->next;}greaterTail->next=NULL;// 链接大小链表：小前大后lessTail->next=greaterHead->next;// 存小链表第一个有效结点，并释放头结点ListNode* newHead=lessHead->next;free(lessHead);free(greaterHead);lessHead=lessTail=NULL;return newHead;
}注意：
1、必须要将大链表的尾指针的next指针置为NULL，否则会成环，报错为超出时间限制：
分析如下：
2、greaterTail->next=NULL 语句必须在 lessTail->next=greaterHead->next语句之前：
假设跳出while循环后的代码顺序如下：
// 链接大小链表：小前大后
lessTail->next=greaterHead->next;
greaterTail->next=NULL;提交报错如下：
这个错误表明程序试图访问一个未正确对齐的内存地址，
通常是由于结构体成员未正确初始化或内存分配问题导致的。
考虑原链表为[1]（单个结点)，x=2的情况：
由于在while循环中仅执行了if分支并没有执行else分支，
greaterHead仅调用malloc申请了空间，并未为其val及next赋值。
此时直接使用greaterTail->next为lessTail->next赋值，会导致赋值为随机值。
令greaterTail->next=NULL 语句在 lessTail->next=greaterHead->next语句之前，可以保证greaterHead和greaterTail被初始化为NULL。
