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.
the key point of this problem is "DO NOT FORGET TO SET NULL".
|
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 |
/** * 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(head == NULL) return
NULL; bool
bBig=false; bool
bSmall=false; ListNode *p=head; ListNode * pBig = NULL; ListNode * pSmall = NULL; ListNode *pHead = NULL; ListNode *pHead2 = NULL; while(p!=NULL) { int
v = p->val; if(v >= x) { if(pBig==NULL) { pBig = p; pHead2 = p; } else { pBig->next=p; pBig = pBig->next; } } if(v < x) { if(pSmall==NULL) { pSmall = p; pHead = p; } else { pSmall->next=p; pSmall = pSmall->next; } } p=p->next; } !!!!!!!!//this is really import, or there will be a circle in linklist!!!!!!!!!! if(pSmall != NULL) { pSmall->next = NULL; } if(pBig != NULL) { pBig->next = NULL; } if(pHead != NULL) { pSmall->next = pHead2; } else { pHead = pHead2; } return
pHead; }}; |
[LeetCode] [Partition List 2012-04-30],布布扣,bubuko.com
[LeetCode] [Partition List 2012-04-30]
原文：http://www.cnblogs.com/xxiao1119/p/3747208.html