forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathpartitionList.cpp
More file actions
87 lines (77 loc) · 1.96 KB
/
partitionList.cpp
File metadata and controls
87 lines (77 loc) · 1.96 KB
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
76
77
78
79
80
81
82
83
84
85
86
87
// Source : https://oj.leetcode.com/problems/partition-list/
// Author : Hao Chen
// Date : 2014-06-21
/**********************************************************************************
*
* 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 <stdio.h>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode *partition(ListNode *head, int x) {
ListNode fakeHead(0);
fakeHead.next = head;
head = &fakeHead;
ListNode *pos = NULL;
for(ListNode *p = head; p!=NULL && p->next!=NULL; ){
if (!pos && p->next->val >= x){
pos = p;
p=p->next;
continue;
}
if (pos && p->next->val < x){
ListNode *pNext = p->next;
p->next = pNext->next;
pNext->next = pos->next;
pos->next = pNext;
pos = pNext;
continue;
}
p=p->next;
}
return head->next;
}
void printList(ListNode* h)
{
while(h!=NULL){
printf("%d ", h->val);
h = h->next;
}
printf("\n");
}
ListNode* createList(int a[], int n)
{
ListNode *head=NULL, *p=NULL;
for(int i=0; i<n; i++){
if (head == NULL){
head = p = new ListNode(a[i]);
}else{
p->next = new ListNode(a[i]);
p = p->next;
}
}
return head;
}
int main()
{
//int a[] = {1}; int x =2;
//int a[] = {2,3,1}; int x=2;
int a[] = {3,1,2}; int x=3;
ListNode* p = createList(a, sizeof(a)/sizeof(int));
printList(p);
p = partition(p, x);
printList(p);
return 0;
}