-
Notifications
You must be signed in to change notification settings - Fork 0
/
PartitionList.hpp
75 lines (66 loc) · 1.2 KB
/
PartitionList.hpp
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//Partition List
//
//Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
//
//You should preserve the original relative order of the nodes in each of the two partitions.
//
//For example,
//Given 1->4->3->2->5->2 and x = 3,
//return 1->2->2->4->3->5.
#include "LinkList.hpp"
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
if (NULL == head)
return head;
ListNode* p = head;
ListNode* q = NULL;
ListNode* prev = NULL;
if (NULL != p->next)
q = p->next;
else
return head;
while (NULL != q && p->val < x && q->val < x)
{
p = q;
q = q->next;
}
if (NULL == q)
return head;
if (p->val < x && q->val >= x)
prev = p;
while (NULL != q)
{
if (q->val < x)
{
p->next = q->next;
if (NULL != prev)
{
q->next = prev->next;
prev->next = q;
}
else
{
q->next = head;
head = q;
}
prev = q;
q = p->next;
}
else
{
p = q;
q = q->next;
}
}
return head;
}
};