-
Notifications
You must be signed in to change notification settings - Fork 0
/
sortBinaryLL.cpp
106 lines (77 loc) · 1.81 KB
/
sortBinaryLL.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
95
96
97
98
99
100
101
102
103
104
105
106
/*
Sort Binary Linked List
Problem Description
Given a Linked List A consisting of N nodes.
The Linked List is binary i.e data values in the linked list nodes consist of only 0's and 1's.
You need to sort the linked list and return the new linked list.
NOTE:
Try to do it in constant space.
Problem Constraints
1 <= N <= 105
A.val = 0 or A.val = 1
Input Format
First and only argument is the head pointer of the linkedlist A.
Output Format
Return the head pointer of the new sorted linked list.
Example Input
Input 1:
1 -> 0 -> 0 -> 1
Input 2:
0 -> 0 -> 1 -> 1 -> 0
Example Output
Output 1:
0 -> 0 -> 1 -> 1
Output 2:
0 -> 0 -> 0 -> 1 -> 1
Example Explanation
Explanation 1:
The sorted linked list looks like:
0 -> 0 -> 1 -> 1
Explanation 2:
The sorted linked list looks like:
0 -> 0 -> 0 -> 1 -> 1
*/
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
ListNode* Solution::solve(ListNode* A) {
ListNode* zeroHead = NULL;
ListNode* zeroTail = NULL;
ListNode* oneHead = NULL;
ListNode* oneTail = NULL;
while(A){
if(A->val==0){
if(zeroHead==NULL){
zeroHead = zeroTail = A;
}else{
zeroTail->next = A;
zeroTail = zeroTail->next;
}
}else{
if(oneHead==NULL){
oneHead = oneTail = A;
}else{
oneTail->next = A;
oneTail = oneTail->next;
}
}
A = A -> next;
}
if(zeroTail == NULL) return oneHead;
zeroTail->next = oneHead;
if(oneTail == NULL) return zeroHead;
oneTail->next = NULL;
return zeroHead;
}
Time taken: 3 min.
Score:
200
/
200
C++17 (Gcc-9.2)
Old view