分割鏈表

給你一個鏈表的頭節點 head 和一個特定值 x ，請你對鏈表進行分隔，使得所有 小于 x 的節點都出現在 大于或等于 x 的節點之前。
你不需要 保留 每個分區中各節點的初始相對位置。

示例 1：
輸入：head = [1,4,3,2,5,2], x = 3
輸出：[1,2,2,4,3,5]示例 2：
輸入：head = [2,1], x = 2
輸出：[1,2]

解題思路：
使用雙指針的思路來解決鏈表分區問題，通過創建兩個新鏈表分別存儲小于 x 和大于等于 x 的節點，最后合并這兩個鏈表得到結果。

1. 虛擬頭節點初始化：分別為值小于 x 和大于等于 x 的節點創建虛擬頭節點 head1 和 head2，并將它們的 next 指針初始化為 NULL。
2. 遍歷原鏈表：遍歷原鏈表，根據節點值與 x 的大小關系，將節點連接到對應的鏈表尾部。
3. 斷開節點連接：在將節點連接到新鏈表后，斷開該節點與原鏈表的連接，避免形成環。
4. 合并鏈表：將存儲大于等于 x 節點的鏈表連接到存儲小于 x 節點的鏈表尾部。
5. 釋放虛擬頭節點：釋放創建的兩個虛擬頭節點。
6. 返回結果：返回合并后鏈表的頭節點。

struct ListNode* partition(struct ListNode* head, int x) {// 小的放 list1，大的放 list2struct ListNode* head1,* tail1,* head2,* tail2;head1 = tail1 = (struct ListNode*)malloc(sizeof(struct ListNode));head2 = tail2 = (struct ListNode*)malloc(sizeof(struct ListNode));// 初始化虛擬頭節點的 next 指針head1->next = NULL;head2->next = NULL;struct ListNode* cur = head;while (cur) {struct ListNode* next = cur->next; // 保存當前節點的下一個節點if (cur->val < x) {tail1->next = cur;tail1 = tail1->next;tail1->next = NULL; // 斷開當前節點與原鏈表的連接} else {tail2->next = cur;tail2 = tail2->next;tail2->next = NULL; // 斷開當前節點與原鏈表的連接}cur = next;}tail1->next = head2->next;// 合并兩個鏈表struct ListNode* result = head1->next;// 保存結果鏈表頭節點free(head1);// 釋放虛擬頭節點free(head2);return result;
}