forked from TonnyL/Windary
-
Notifications
You must be signed in to change notification settings - Fork 0
/
PartitionList.go
63 lines (56 loc) · 1.13 KB
/
PartitionList.go
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
package PartitionList
//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.
//
//Accepted.
type ListNode struct {
Val int
Next *ListNode
}
func partition(head *ListNode, x int) *ListNode {
node := head
var greater *ListNode
var greaterHead *ListNode
var less *ListNode
var lessHead *ListNode
for ; node != nil; {
if node.Val < x {
if less == nil {
less = &ListNode{
Val: node.Val,
}
lessHead = less
} else {
less.Next = &ListNode{
Val: node.Val,
}
less = less.Next
}
} else {
if greater == nil {
greater = &ListNode{
Val: node.Val,
}
greaterHead = greater
} else {
greater.Next = &ListNode{
Val: node.Val,
}
greater = greater.Next
}
}
node = node.Next
}
if greaterHead == nil {
return lessHead
} else if lessHead == nil {
return greaterHead
}
less.Next = greaterHead
return lessHead
}