-
Notifications
You must be signed in to change notification settings - Fork 0
/
096. 链表划分.cpp
94 lines (87 loc) · 2.21 KB
/
096. 链表划分.cpp
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
88
89
90
91
92
93
94
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
// class Solution {
// public:
// /*
// * @param head: The first node of linked list
// * @param x: An integer
// * @return: A ListNode
// */
// ListNode * partition(ListNode * head, int x) {
// // write your code here
// ListNode *one = new ListNode(0);
// ListNode *two = new ListNode(0);
// one->next = NULL;
// two->next = NULL;
// ListNode *ptOne = one;
// ListNode *ptTwo = two;
// ListNode *original = head;
// ListNode *temp;
// while(original != NULL)
// {
// if(original->val < x)
// {
// ptOne->next = original;
// ptOne = original;
// }
// else
// {
// ptTwo->next = original;
// ptTwo = original;
// }
// original = original->next;
// }
// ptOne->next = two->next;
// ptTwo->next = NULL;
// temp = one->next;
// delete one;
// delete two;
// return temp;
// }
// };
class Solution {
public:
/*
* @param head: The first node of linked list
* @param x: An integer
* @return: A ListNode
*/
ListNode * partition(ListNode * head, int x) {
// write your code here
ListNode *A = new ListNode(0);
ListNode *B = new ListNode(0);
ListNode *p = head, *pA=A, *pB=B, *temp;
while(p!=NULL)
{
temp = p->next;
if(p->val < x)
{
pA->next = p;
p->next = NULL;
pA = pA->next;
}
else
{
pB->next = p;
p->next = NULL;
pB = pB->next;
}
p = temp;
}
pA->next = B->next;
delete B;
temp = A->next;
delete A;
return temp;
}
};