题目描述
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
题解
虚拟头指针、双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| ListNode* partition(ListNode* head, int x) {
if (!head)return NULL;
ListNode* prehead;
prehead = new ListNode(x - 1);
prehead->next = head;
ListNode *t = prehead;
while (t->next&&t->next->val < x)t = t->next;
if (t->next == NULL)return head;
ListNode *position = t;
ListNode *current = t->next;
while (current->next != NULL)
{
if (current->next->val < x)
{
ListNode *tmp = current->next;
current->next = current->next->next;
tmp->next = position->next;
position->next = tmp;
position = position->next;
}
else
current = current->next;
}
return prehead->next;
}
|