题目概要
将链表中小于某个值的结点移到链表最前方。
原题链接
题目解析
简单的数据结构题，解题思路如下：
- 迭代链表，将之分为两部分，一条小于x，一条不小于x
- 合并两条链表
复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
ListNode* nextNode(ListNode*& head) {
if (head == NULL)
return NULL;
ListNode* current = head;
head = head->next;
current->next = NULL;
return current;
}
void pushBack(ListNode*& head, ListNode*& tail, ListNode* node) {
if (head == NULL || tail == NULL) {
head = tail = node;
return;
}
tail->next = node;
tail = node;
return;
}
public:
ListNode* partition(ListNode* head, int x) {
if (head == NULL || head->next == NULL)
return head;
ListNode* less = NULL;
ListNode* lessTail = NULL;
ListNode* notLess = NULL;
ListNode* notLessTail = NULL;
ListNode* current = NULL;
while(head != NULL) {
current = nextNode(head);
if (current->val < x) {
pushBack(less, lessTail, current);
}
else {
pushBack(notLess, notLessTail, current);
}
}
if (less == NULL)
return notLess;
if (lessTail != NULL)
lessTail->next = notLess;
return less;
}
};
广告区域
本人和小伙伴们承接各种软件项目，有需求的可以联系我们。
QQ: 2992073083
