给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
ListNode *lessHead = new ListNode(0); // 创建一个虚拟头节点,用于存放小于 x 的节点
ListNode *greaterHead = new ListNode(0); // 创建一个虚拟头节点,用于存放大于等于 x 的节点
ListNode *lessPtr = lessHead; // 指向小于 x 的节点的尾部
ListNode *greaterPtr = greaterHead; // 指向大于等于 x 的节点的尾部
while (head != nullptr) {
if (head->val < x) {
lessPtr->next = head;
lessPtr = lessPtr->next;
} else {
greaterPtr->next = head;
greaterPtr = greaterPtr->next;
}
head = head->next;
}
greaterPtr->next = nullptr; // 将大于等于 x 的链表尾部置为空
lessPtr->next = greaterHead->next; // 将小于 x 的链表与大于等于 x 的链表连接起来
ListNode* result = lessHead->next; // 返回拼接后的链表头节点
delete lessHead;
delete greaterHead;
return result;
}
首先创建两个虚拟头节点 lessHead 和 greaterHead,分别用于存放小于 x 的节点和大于等于 x 的节点。然后通过遍历原链表,将节点根据其值的大小分别连接到相应的链表中。最后,将小于 x 的链表与大于等于 x 的链表连接起来,并返回拼接后的链表头节点。
代码中使用了四个指针,lessHead 和 greaterHead 分别表示两个链表的虚拟头节点,lessPtr 指向小于 x 的链表的尾部,greaterPtr 指向大于等于 x 的链表的尾部。通过这些指针的操作,可以在保持原有相对位置的同时完成链表的分隔。
最后,释放动态分配的内存,避免内存泄漏。