现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针
时间: 2023-04-10 19:03:39 浏览: 84
可以使用双指针法,一个指针指向小于x的结点,一个指针指向大于等于x的结点,最后将两部分链表拼接起来即可。具体代码如下:
ListNode* partition(ListNode* pHead, int x) {
ListNode* smallHead = new ListNode(0); // 小于x的结点链表的头结点
ListNode* smallTail = smallHead; // 小于x的结点链表的尾结点
ListNode* bigHead = new ListNode(0); // 大于等于x的结点链表的头结点
ListNode* bigTail = bigHead; // 大于等于x的结点链表的尾结点
ListNode* cur = pHead;
while (cur != nullptr) {
if (cur->val < x) {
smallTail->next = cur;
smallTail = cur;
} else {
bigTail->next = cur;
bigTail = cur;
}
cur = cur->next;
}
// 拼接两部分链表
smallTail->next = bigHead->next;
bigTail->next = nullptr;
ListNode* newHead = smallHead->next;
delete smallHead;
delete bigHead;
return newHead;
}
阅读全文