NL
BAN USER- 1of 1 vote
AnswersGiven the following linked list: 1 -> 2 -> 3-> 4-> 5-> 6 reverse the list each N nodes. eg. if N = 3 the output should be 3-> 2-> 1-> 6-> 5-> 4. Also provide a mechanism to prevent errors. For the same example, if N = 4, the result should be: 4-> 3-> 2-> 1-> 5-> 6 (The last two nodes can't be reversed)
- NL in United States| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven a linked list: 5 -> 4 -> 3 -> 2 -> 1, produce the following output: 4 -> 2 -> 0 -> 2 -> 1 by substracting the 1st node with nth node, the 2nd with nth -1 node, etc... Only apply the stated action on the first half of the list
- NL in United States| Report Duplicate | Flag | PURGE
Software Engineer / Developer Coding
Java approach
public static void main(String[] args) {
Integer[] arr = {3, 1, 4, 5, 6};
Integer[] rep = {1, 9, 5, 2, 3};
maximize(arr, rep);
}
private static void maximize(Integer[] arr, Integer[] rep) {
Comparator<Integer> comparator = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 > o2 ? -1 : 1;
}
};
Arrays.sort(rep, comparator);
int repIndex = 0;
for(int i = 0; i < arr.length; i++){
if(arr[i] < rep[repIndex]){
arr[i] = rep[repIndex];
repIndex++;
}
}
for(int i : arr)
System.out.println(i);
}
Java approach:
public static void main(String[] args) {
int arr[] = {1, 0, 2, 0, 0, 3, 4};
System.out.println(swapNonZeros(arr));
for(int i : arr)
System.out.print(i + " ");
System.out.println();
}
private static int swapNonZeros(int[] arr) {
int zero_index = 0;
for(int i = 0; i < arr.length; i++){
while(arr[i] != 0)
i++;
zero_index = i;
i++;
while(arr[i] == 0){
i++;
if(i == arr.length)
return arr.length - zero_index;
}
swap(arr, i, zero_index);
i = zero_index;
}
return arr.length - zero_index;
}
private static void swap(int[] arr, int i, int zero_index) {
int aux = arr[i];
arr[i] = arr[zero_index];
arr[zero_index] = aux;
}
Output:
3
1 2 3 4 0 0 0
O(n^2) in java:
public static void main(String[] args) {
int[] arr = {3, 4, 7, 1, 2, 9, 8};
findFactors(arr);
}
static class Factors {
public Factors(int A, int B) {
this.A = A;
this.B = B;
}
int A;
int B;
}
public static void findFactors(int[] arr) {
Map<Integer, Factors> m = new HashMap<>();
int aux = 0;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
aux = arr[i] + arr[j];
if (m.containsKey(aux)) {
System.out.println(arr[i] + " + " + arr[j] + " = " + arr[m.get(aux).A] + " + " + arr[m.get(aux).B]);
System.out.println("(" + i + "," + j + "," + m.get(aux).A + "," + m.get(aux).B + ")");
} else {
m.put(aux, new Factors(i, j));
}
}
}
}
Output:
4 + 7 = 3 + 8
(1,2,0,6)
4 + 1 = 3 + 2
(1,3,0,4)
4 + 8 = 3 + 9
(1,6,0,5)
1 + 9 = 3 + 7
(3,5,0,2)
1 + 8 = 7 + 2
(3,6,2,4)
2 + 9 = 3 + 8
(4,5,0,6)
2 + 8 = 3 + 7
(4,6,0,2)
This is called "The Conway Sequence"
My approach in Java:
public static void main(String[] args) {
conwaySequence(5);
}
private static void conwaySequence(int num) {
if(num < 1)
return;
System.out.println("1");
String output = "1";
String new_output = "";
int current_count = 0;
char current_char;
for(int i = 1; i < num; i++){
current_char = output.charAt(0);
for(int j = 0; j < output.length(); j++){
if(output.charAt(j) == current_char)
current_count++;
else{
new_output += Integer.toString(current_count) + current_char;
current_char = output.charAt(j);
current_count = 1;
}
}
output = new_output + Integer.toString(current_count) + current_char;
new_output = "";
current_count = 0;
System.out.println(output);
}
}
Java approach:
public static void main(String[] args) {
allSubsets(4, "");
}
private static void allSubsets(int num, String out) {
if(num == 0){
System.out.println(out);
} else if (num > 0){
for(int i = 1; i <= num; i++)
allSubsets(num - i, out + " " + Integer.toString(i));
}
}
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1
4
public static void main(String[] args) {
pascalTriangle(0, 5, null);
}
private static void pascalTriangle(int start, int end, int [] old) {
if(start == end + 1)
return;
int [] arr = new int[start + 1];
arr[0] = 1;
arr[arr.length - 1] = 1;
for(int i = 1; i < arr.length - 1; i++)
arr[i] = old[i - 1] + old[i];
for(int i : arr)
System.out.print(i + " ");
System.out.println("");
pascalTriangle(start + 1, end, arr);
}
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
My proposal in Java:
{
public static void main(String[] args) throws FileNotFoundException {
System.out.println(printExpression("2*3*5+8+2+3"));
}
private static int printExpression(String input) {
Deque<Integer> digits = new ArrayDeque<Integer>();
Deque<Character> operators = new ArrayDeque<Character>();
for(int i = 0; i < input.length(); i++){
if(input.charAt(i) != '*' && input.charAt(i) != '+')
digits.addLast(input.charAt(i) - '0');
else if(input.charAt(i) == '*')
operators.addLast('*');
else
operators.addLast('+');
}
int operator_size = operators.size();
for(int i = 0; i < operator_size; i++){
if(operators.getFirst() == '*'){
int a = digits.getFirst();
digits.removeFirst();
int b = digits.getFirst();
digits.removeFirst();
operators.removeFirst();
digits.addFirst(a * b);
} else {
operators.removeFirst();
digits.addLast(digits.getFirst());
digits.removeFirst();
}
}
int sum = 0;
while(!digits.isEmpty()){
sum += digits.getFirst();
digits.removeFirst();
}
return sum;
}
}
- NL March 11, 2015A Java approach:
public static void main(String[] args) {
findIndex("abcd", "abcdefcdbacd");
}
private static void findIndex(String s1, String s2) {
Map<Character, Boolean> map = new HashMap<>();
for(int i = 0; i < s1.length(); i++)
map.put(s1.charAt(i), true);
int counter = 0;
for(int i = 0; i <= s2.length() - s1.length() ; i++){
if(map.containsKey(s2.charAt(i))){
map.put(s2.charAt(i), false);
counter++;
for(int j = i + 1; j < s1.length() + i; j++){
if(map.containsKey(s2.charAt(j))){
map.put(s2.charAt(j), false);
counter++;
}
else
break;
}
if(counter == s1.length())
System.out.println(i);
resetMap(map);
counter = 0;
}
}
}
private static void resetMap(Map<Character, Boolean> map) {
for(Object o : map.entrySet()){
Map.Entry me = (Map.Entry) o;
me.setValue(true);
}
}
Output: 0, 6, 7, 8. <-- Please notice this should be the correct output in the problem's description
- NL July 26, 2014C++ approach:
#include <iostream>
using namespace std;
void Brackets(string output, int open, int close, int pairs)
{
if((open==pairs)&&(close==pairs))
{
cout<<output<<endl;
}
else
{
if(open<pairs)
{
Brackets(output + "(", open+1, close, pairs);
}
if(close<open)
{
Brackets(output + ")", open, close+1, pairs);
}
}
}
int main(int argc, const char * argv[])
{
Brackets("",0,0,3);
}
In C++:
#include <iostream>
#include <sstream>
using namespace std;
void combinationsString(string word, string out, int start)
{
for(int i = start; i < word.length(); i++)
{
out += word.at(i);
cout << out << endl;
combinationsString(word, out, i + 1);
out.erase(out.length() - 1, 1);
}
}
int main(int argc, const char * argv[])
{
combinationsString("abc", "", 0);
//Output: a, ab, abc, ac, b, bc, c
}
My proposal in Java.
public static int max(int a, int b){
return a > b ? a : b;
}
private static int biggestSum(int[] first, int[] second, int n, int sum, int current) {
if((n == first.length && current == 1) || (n == second.length && current == 2))
return sum;
else if(n >= first.length)
return sum += biggestSum(first, second, n + 1, sum, 2) + second[n];
else if(n >= second.length)
return sum += biggestSum(first, second, n + 1, sum, 1) + first[n];
if(first[n] == second[n])
sum += max(biggestSum(first, second, n + 1, sum, 1) + first[n], biggestSum(first, second, n + 1, sum, 2) + second[n]);
else if(current == 1)
sum += biggestSum(first, second, n + 1, sum, 1) + first[n];
else if(current == 2)
sum += biggestSum(first, second, n + 1, sum, 2) + second[n];
return sum;
}
public static void main(String [] args){
int first[] = {3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62};
int second[] = {1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100};
int max_sum = max(biggestSum(first, second, 0, 0, 1), biggestSum(first, second, 0, 0, 2));
System.out.println(max_sum); // 450
}
Java approach for this. I did it to move all zeros to the right and to the left ;) :
public static void main(String [] args){
int arr[] = {0, 0, 1, 0, 1, 3, 0, 4, 0, 0, 5};
transformArrayToRight(arr);
for(Integer i : arr)
System.out.print(i + " ");
System.out.println("");
}
private static void transformArrayToLeft(int[] arr) {
Deque d = new LinkedList();
for(int i = 0; i < arr.length; i++){
if(arr[i] != 0)
d.addLast(arr[i]);
arr[i] = 0;
}
int i = 0;
while(!d.isEmpty()){
arr[i] = (int) d.getFirst();
d.removeFirst();
i++;
}
}
private static void transformArrayToRight(int[] arr) {
Deque d = new LinkedList();
for(int i = 0; i < arr.length; i++){
if(arr[i] != 0)
d.addLast(arr[i]);
arr[i] = 0;
}
int i = arr.length - 1;
while(!d.isEmpty()){
arr[i] = (int) d.getLast();
d.removeLast();
i--;
}
}
C++ proposal:
{
void adjustList(node * ¤t, node * runner, int & length)
{
if(runner == NULL)
{
length /= 2;
return;
}
length++;
adjustList(current, runner->next, length);
if(length >= 0)
{
current->data = runner->data - current->data;
current = current->next;
length--;
}
}
int main()
{
node * head = NULL;
head = addNode(head, 8);
head = addNode(head, 7);
head = addNode(head, 6);
head = addNode(head, 5);
head = addNode(head, 4);
head = addNode(head, 3);
head = addNode(head, 2);
node * current = head;
int length = -1;
adjustList(current, head, length);
printNode(head);
//output: -6 -4 -2 0 4 3 2
}
}
- NL June 25, 2014My proposal in Java:
{
class Node{
public int data;
public int count;
public Node p_left;
public Node p_right;
}
public class BSTCustom {
private Node tree;
private int val;
private Node processValue(Node root, int value, int counter){
if(root == null){
root = new Node();
root.data = value;
root.count = counter + 1;
val = root.count;
return root;
}
if(root.data < value){
root.p_right = processValue(root.p_right, value, root.count);
}
else if(root.data == value){
root.count++;
val = root.count;
updateSons(root.p_right);
}
else{
int aux = root.count;
root.count++;
root.p_left = processValue(root.p_left, value, aux - 2);
updateSons(root.p_right);
}
return root;
}
private void updateSons(Node root){
if(root == null)
return;
root.count++;
updateSons(root.p_left);
updateSons(root.p_right);
}
public BSTCustom(){
tree = null;
}
public int processValue(int value, int counter) {
tree = processValue(tree, value, counter);
return val;
}
}
---
public class Main {
public static void main(String[] args) {
BSTCustom bst = new BSTCustom();
int arr[] = {1, 3, 2, 4, 5, 4, 2};
int out[] = new int[arr.length];
for(int i = arr.length - 1; i >= 0 ; i--)
out[i] = bst.processValue(arr[i], -1);
for(int i = 0; i < arr.length; i++)
System.out.print(out[i] + " ");
System.out.println("");
//Output: 0 2 1 2 2 1 0
}
}
}
- NL June 23, 2014Java approach:
{
public static String excelColumnEquivalent(int n){
if(n < 0)
return "Invalid number";
String out = "";
StringBuffer sb = new StringBuffer();
while(n > 0){
n--;
sb.append(Character.toChars(n % 26 + 'a'));
out = sb.toString() + out;
sb.setLength(0);
n /= 26;
}
return out;
}
}
- NL June 02, 2014Java approach. Takes O(n!):
{
public static void permutations(String word, String perm){
if(word.equals("")){
System.out.println(perm);
return;
}
for(int i = 0; i < word.length(); i++){
StringBuffer word_util = new StringBuffer(word);
word_util.deleteCharAt(i);
String perm_util = perm;
perm_util += word.charAt(i);
permutations(word_util.toString(), perm_util);
}
}
}
- NL June 02, 2014My proposal in C++:
{
#include <iostream>
using namespace std;
enum obstacles {door, wall};
class Grid
{
private:
char ** spaces;
int size_y;
int size_x;
public:
Grid(int y, int x) : size_y(y), size_x(x)
{
spaces = new char*[size_y];
for(int i = 0; i < size_y; i++)
spaces[i] = new char[size_x];
for(int i = 0; i < size_y; i++)
for(int j = 0; j < size_x; j++)
spaces[i][j] = '?';
}
void printGrid()
{
for(int y = 0; y < size_y; y++)
{
cout << "|";
for(int x = 0; x < size_x; x++)
cout << spaces[y][x] << "|";
cout << endl;
}
}
void addPoint(int y, int x, obstacles o)
{
if(o == door)
spaces[y][x] = 'D';
else
spaces[y][x] = 'W';
}
void spread(int y, int x, int value, bool flag)
{
if(y >= size_y || y < 0 || x >= size_x || x < 0)
return;
if(flag)
{
flag = false;
goto special;
}
if(spaces[y][x] != 'D' && spaces[y][x] != 'W' && value < spaces[y][x])
{
spaces[y][x] = value;
special:
{}
spread(y + 1, x, value + 1, flag);
spread(y - 1, x, value + 1, flag);
spread(y, x + 1, value + 1, flag);
spread(y, x - 1, value + 1, flag);
}
}
void fillTable()
{
for(int y = 0; y < size_y; y++)
{
for(int x = 0; x < size_x; x++)
{
if(spaces[y][x] == 'D')
{
spread(y, x, '0', true);
}
}
}
}
};
int main()
{
Grid g(5, 5);
g.addPoint(2, 1, door);
g.addPoint(2, 2, wall);
g.addPoint(2, 3, wall);
g.addPoint(1, 3, wall);
g.addPoint(0, 4, door);
g.printGrid();
g.fillTable();
cout << endl;
g.printGrid();
}
}
Output:
|?|?|?|?|D|
|?|?|?|W|?|
|?|D|W|W|?|
|?|?|?|?|?|
|?|?|?|?|?|
|3|2|2|1|D|
|2|1|2|W|1|
|1|D|W|W|2|
|2|1|2|3|3|
|3|2|3|4|4|
C++ proposal. I took into account the fact that swaps can only be performed on adjacent locations:
{
void swapMax(int * arr, int target_position, int current_position)
{
int aux = 0;
for(int i = current_position; i > target_position; i--)
{
aux = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = aux;
}
}
void maximizeArray(int * arr, int length, int swaps)
{
if(swaps == 0)
return;
for(int i = 0; i < length; i++)
{
int max_index = 0, max = -INT32_MAX;
int limit = (swaps + i) > length ? length : swaps + i;
for(int j = i; j <= limit; j++)
{
if(arr[j] > max)
{
max = arr[j];
max_index = j;
}
}
swaps -= (max_index - i);
swapMax(arr, i, max_index);
if(swaps == 0)
break;
}
}
int main()
{
int arr[]={1,5,2,9,3,7,2,8,9,3};
int length = sizeof(arr) / sizeof(int);
maximizeArray(arr, length, 5);
for(int i = 0; i < length; i++)
cout << arr[i] << " ";
cout << endl;
//9 5 2 1 3 7 2 8 9 3
return 0;
}
}
- NL May 12, 2014C++ approach. O(nlog(n)) time complexity:
{
int factorial(int n)
{
if(n == 1)
return 1;
return n * factorial(n - 1);
}
void getPermutations(string word, string perm, int * permutations, int & j)
{
if(word.empty())
{
permutations[j] = stoi(perm);
j++;
return;
}
for(int i = 0; i < word.length(); i++)
{
string word_util = word;
word_util.erase(i, 1);
string perm_util = perm;
perm_util += word[i];
getPermutations(word_util, perm_util, permutations, j);
}
}
int binarySearch(int * arr, int value, int left, int right)
{
if(left > right)
return -1;
int mid = (left + right) / 2;
if(value == arr[mid])
return mid;
else if(value < arr[mid])
return binarySearch(arr, value, left, mid - 1);
else
return binarySearch(arr, value, mid + 1, right);
}
int numberRank(int * arr, int length, int x)
{
string aux = "";
for(int i = 0; i < length; i++)
aux += to_string(arr[i]);
int fact = factorial(length);
int * permutations = new int[fact];
int j = 0;
getPermutations(aux, "", permutations, j);
sort(permutations, permutations + fact);
return binarySearch(permutations, x, 0, fact - 1) + 1;
}
int main(int argc, const char * argv[])
{
int arr[] = {4, 1, 5};
int x = 541;
cout << numberRank(arr, sizeof(arr) / sizeof(int), x) << endl;
//returns : 4
}
}
- NL May 11, 2014C++ approach using stacks. Runs in O(n):
{
string erase(string word, stack<int> mul)
{
while(!mul.empty())
{
word[mul.top()] = ' ';
mul.pop();
}
return word;
}
void filter(string & word)
{
for(int i = 0; i < word.length(); i++)
if(word[i] == ' ')
{
word.erase(i, 1);
i--;
}
}
string analyze(string word)
{
stack<int> saver;
stack<int> mul;
stack<int> sum;
stack<char> signs;
for(int i = 0; i < word.length(); i++)
{
if(word[i] == '(')
saver.push(i);
else if(word[i] == '*' || word[i] == '/')
{
signs.push(word[i]);
if(mul.size() > 0)
{
mul.push(saver.top());
saver.pop();
}
}
else if(word[i] == ')')
{
if(signs.top() == '*' || signs.top() == '/')
mul.push(i);
else
sum.push(i);
signs.pop();
}
else if(word[i] == '+' || word[i] == '-')
{
signs.push(word[i]);
if(sum.size() > 0)
{
sum.push(saver.top());
saver.pop();
}
}
}
word = erase(word, mul);
filter(word);
return word;
}
}
- NL May 09, 2014I've noticed there are cases where more than one solution exists. This is a C++ approach that takes care of such cases:
{
using namespace std;
void print(int * arr, int length)
{
cout << "Solution found" << endl;
for(int i = 0; i < length; i++)
cout << arr[i] << " ";
cout << endl;
}
void makeArrayUtil(int val, int * arr, int length, int max)
{
if(val > max)
{
print(arr, length);
return;
}
for(int i = 0 ; i < length; i++)
{
if(arr[i] == 0 && arr[i + val + 1] == 0 && (i + val + 1) < length)
{
arr[i] = val;
arr[i + val + 1] = val;
makeArrayUtil(val + 1, arr, length, max);
arr[i] = 0;
arr[i + val + 1] = 0;
}
}
}
void makeArray(int input)
{
int * output = new int[2 * input];
int length = 2 * input;
makeArrayUtil(1, output, length, input);
}
int main(int argc, const char * argv[])
{
makeArray(7);
return 0;
}
}
- NL May 09, 2014If you perform a slight modification on the nodes of your tree, you could store both the data and the level (depth) of the node
{
struct node
{
int data;
int level;
node* p_left;
node* p_right;
};
}
Once you have your tree built and having in mind that each node stores its level, you could perform an iterative preorder traversal. Once you find the desired value, you return from the function:
{
void preOrder(node * root, int value, int * path, int & level)
{
if(root == NULL)
return;
stack<node*> s;
s.push(root);
while(!s.empty())
{
node * aux = s.top();
s.pop();
path[aux->level] = aux->data;
if(aux->data == value)
{
level = aux->level;
return;
}
if(aux->p_right != NULL)
s.push(aux->p_right);
if(aux->p_left != NULL)
s.push(aux->p_left);
}
}
}
The rest is just cout'in the path array from 0 to level
Using a struct and a list:
{
struct element
{
int key;
int value;
};
class LRUcache
{
private:
int max_size;
int current_size;
list<element*> l;
public:
LRUcache()
{
max_size = 10;
current_size = 0;
}
int get(int key)
{
int value = -INT32_MAX;
for(list<element*>::iterator it = l.begin(); it != l.end(); it++)
{
if((*it)->key == key)
{
value = (*it)->value;
list<element*>::iterator aux = it;
l.erase(it);
l.push_front(*aux);
return value;
}
}
return value;
}
void put(int key, int value)
{
element * e = new element;
e->key = key;
e->value = value;
if(current_size == max_size)
{
cout << "replacing oldest value: " << l.back()->key << " " << l.back()->value << endl;
delete l.back();
l.pop_back();
current_size--;
}
l.push_front(e);
current_size++;
}
};
}
- NL May 07, 2014C++ approach. o(n) time complexity solution.
{
int determineLength(int * arr, int length)
{
int max_extension = 0;
map<int, int, cmp> m;
for(int i = 0; i < length; i++)
m[arr[i]]++;
map<int, int>::iterator stop = m.end();
stop--;
int key, value;
for(map<int, int>::iterator it = m.begin(); it != stop; it++)
{
key = it->first;
value = it->second;
it++;
if(it->first - key <= 1)
if(it->second + value > max_extension)
max_extension = it->second + value;
it--;
}
return max_extension;
}
}
- NL May 07, 2014Python approach without using "in":
{
def findDuplicates(arr1, arr2):
storage = [[] for i in range(256)]
for i in arr1:
storage[i] = 1;
for i in arr2:
if(storage[i] == 1):
print i
def main():
arr1 = [4, 5, 32, 110]
arr2 = [13, 42, 32, 191, 93, 4]
findDuplicates(arr1, arr2)
}
- NL May 05, 2014C++ approach. The list could be given in any order (i.e. "ybgrrgbyrrggbbyy") as well as the pattern (i.e. "gbyr"). This function will order the list without declaring additional nodes but we will have to use a map. NOTE: the amount of nodes in the list has to be a multiple of the length of the patttern.
{
void orderList(string pattern)
{
map<char, list<node*>> dictionary;
current = head;
node * prev;
int counter = 0;
while(current->next != NULL)
{
dictionary[current->data].push_back(current);
prev = current;
current = current->next;
prev->next = NULL;
counter++;
}
prev = dictionary[pattern[0]].front();
dictionary[pattern[0]].pop_front();
counter--;
head = prev;
int i = 1;
while(counter > 0)
{
current = dictionary[pattern[i]].front();
dictionary[pattern[i]].pop_front();
prev->next = current;
prev = current;
i++;
if(i == pattern.length())
i = 0;
counter--;
}
//current->next = head; //make list circular again
}
}
- NL May 05, 2014C++ function:
{
int * maxSequence(int * arr, int length)
{
int max = 0, start = 0, end = 0, actual_start = 0, sum = 0;
for(int i = 0; i < length; i++)
{
sum += arr[i];
if(sum < 0)
{
sum = 0;
start = i + 1;
}
else if(sum > max)
{
max = sum;
end = i;
actual_start = start;
}
}
int extension = end - actual_start + 1;
int * result = new int[extension];
for(int i = 0; i < (extension); i++)
result[i] = arr[i + actual_start];
return result;
}
}
- NL May 05, 2014C++ Approach:
char arr[] = "test test for this exercise";
sort(arr, arr + sizeof(arr) / sizeof(char), [](char a, char b) {return a < b;});
char compare = arr[0];
char letter = arr[0];
int current = 1;
int max = 1;
for(int i = 1; i < sizeof(arr) / sizeof(char); i++)
{
if(compare == arr[i])
current++;
else
{
compare = arr[i];
current = 1;
}
if(current > max)
{
max = current;
letter = compare;
}
}
cout << letter << " " << max << endl;
void spiralTraversal(node * root)
{
deque<node*> son;
son.push_back(root);
bool flag = true;
while (!son.empty())
{
deque<node*> parents = son;
son = *new deque<node*>;
if(flag)
{
for(node* p: parents)
{
if(p->p_left != NULL)
son.push_front(p->p_left);
if(p->p_right != NULL)
son.push_front(p->p_right);
flag = false;
}
}
else
{
for(node* p: parents)
{
if(p->p_right != NULL)
son.push_front(p->p_right);
if(p->p_left != NULL)
son.push_front(p->p_left);
flag = true;
}
}
while(!parents.empty())
{
cout << parents.front()->data << endl;
parents.pop_front();
}
}
}
My solution proposal in C++:
node* sortLists(node* list)
{
node* ptr1=list;
node* ptr2=list;
while((ptr1->data <= ptr1->next->data) && ptr1->next->next!=NULL)
{
ptr1=ptr1->next;
}
node* aux=ptr1;
ptr1=ptr1->next;
aux->next=NULL;
node* new_list=NULL;
while(ptr1!=NULL && ptr2!=NULL)
{
if(ptr2->data<=ptr1->data)
{
new_list=insertData(ptr2->data,new_list);
ptr2=ptr2->next;
}
else
{
new_list=insertData(ptr1->data,new_list);
ptr1=ptr1->next;
}
}
if(ptr1==NULL)
{
while(ptr2!=NULL)
{
new_list=insertData(ptr2->data,new_list);
ptr2=ptr2->next;
}
}
else
{
while(ptr1!=NULL)
{
new_list=insertData(ptr1->data,new_list);
ptr1=ptr1->next;
}
}
return new_list;
}
RepBarbaraLocke, Android test engineer at ABC TECH SUPPORT
Hey, I'm a BarbaraLocke. And I love my work. Apart from this, I am doing some new experiments in ...
Repmirezwanda, Android test engineer at Arista Networks
Computer database administrator with 3+ years of experience working in Gamma Realty . I often plan security measures, making sure that ...
Solution in Java. If, for example, the output is 2l4, this represents a tree with head 2 and a node in the left as 4. It also shows all duplicates. In the example of the question there are 3, so 3 results are printed in the output
Output:
- NL March 05, 20172l4
4
4