Amazon Interview Question SDE1s
Team: Software Development
Country: United States
Interview Type: Phone Interview
import java.util.Iterator;
import java.util.LinkedList;
public class AMZ_Fibonacci {
public static void main(String args[]) {
isFibonacci(10);
LinkedList<Integer> llist = new LinkedList<Integer>();
llist.add(10);
llist.add(15);
llist.add(1);
llist.add(3);
llist.add(5);
llist.add(17);
separateLinkedList(llist);
}
public static void separateLinkedList(LinkedList<Integer> llist) {
if (llist == null) {
return;
}
LinkedList<Integer> fibSeriesList = new LinkedList<Integer>();
LinkedList<Integer> noSeriesList = new LinkedList<Integer>();
Iterator<Integer> ll = llist.iterator();
int num = -1;
while (ll.hasNext()) {
num = ll.next();
if (isFibonacci(num)) {
fibSeriesList.add(num);
} else {
noSeriesList.add(num);
}
}
System.out.println(fibSeriesList);
System.out.println(noSeriesList);
}
public static boolean isFibonacci(int num) {
int num1 = 5 * num * num - 4;
int num2 = 5 * num * num + 4;
boolean result = isPerfectSqr(num1) || isPerfectSqr(num2);
System.out.println("Run Fibonacci Test > " + num + " | Result > " + result);
return result;
}
public static boolean isPerfectSqr(int num) {
int sqrt = (int) Math.sqrt(num);
return sqrt * sqrt == num;
}
}
public class FibonacciNumbers {
public List<Integer> filterByIndex(LinkedList<Integer> numbers) {
if (numbers == null || numbers.isEmpty()) {
return Collections.emptyList();
}
List<Integer> fibonacciNumbers = new ArrayList<>();
Iterator<Integer> iterator = numbers.iterator();
// add first number & remove it
fibonacciNumbers.add(iterator.next());
iterator.remove();
int prevFibIndex = 1;
int nextFibIndex = 2;
int currentIndex = 2;
while (iterator.hasNext() && nextFibIndex > 0) {
Integer number = iterator.next();
if (currentIndex == nextFibIndex) {
// remove number from first list & add it to second list
iterator.remove();
fibonacciNumbers.add(number);
// calculate next fibonacci index number
int tmp = nextFibIndex;
nextFibIndex = prevFibIndex + nextFibIndex;
prevFibIndex = tmp;
}
currentIndex++;
}
return fibonacciNumbers;
}
public static void main(String[] args) {
LinkedList<Integer> input = new LinkedList<>(Arrays.asList(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15));
FibonacciNumbers test = new FibonacciNumbers();
List<Integer> output = test.filterByIndex(input);
System.out.println("Fibonacci: " + output);
System.out.println("Filtered: " + input);
}
}
Implement a linked list split function which is to take a predicate. Use latest std::function feature from C++11. See code on cpluspluslearning-petert.blogspot.co.uk/2015/11/linkedlist-split-linked-list-into.html
Test
bool IsFibonaciNumber(int val)
{
int temp = 5 * val*val;
int root = static_cast<int>(sqrt(temp - 4));
if (root*root == (temp - 4)) {
return true;
}
root = static_cast<int>(sqrt(temp + 4));
if (root*root == (temp + 4)) {
return true;
}
return false;
}
void TestSplitLLAgainstFibonaci()
{
{
LinkedListElement<int>* head = nullptr;
LinkedListElement<int>* fibonaciNodes = nullptr;
LinkedListElement<int>* nonFibonaciNodes = nullptr;
LL_SpiltLinkedList<int>(&head, &fibonaciNodes, &nonFibonaciNodes, IsFibonaciNumber);
assert(fibonaciNodes == nullptr);
assert(nonFibonaciNodes == nullptr);
}
{
std::vector<int> testArr = { 0, 1, 1, 2, 3, 5, 8 };
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
LinkedListElement<int>* fibonaciNodes = nullptr;
LinkedListElement<int>* nonFibonaciNodes = nullptr;
LL_SpiltLinkedList<int>(&head, &fibonaciNodes, &nonFibonaciNodes, IsFibonaciNumber);
assert(fibonaciNodes != nullptr);
assert(nonFibonaciNodes == nullptr);
assert(head == nullptr);
std::vector<int> result;
LL_CopyDataToStdVector(fibonaciNodes, result);
assert(testArr == result);
LL_Delete(&fibonaciNodes);
}
{
std::vector<int> testArr = { 4, 6, 7, 9, 10 };
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
LinkedListElement<int>* fibonaciNodes = nullptr;
LinkedListElement<int>* nonFibonaciNodes = nullptr;
LL_SpiltLinkedList<int>(&head, &fibonaciNodes, &nonFibonaciNodes, IsFibonaciNumber);
assert(fibonaciNodes == nullptr);
assert(nonFibonaciNodes != nullptr);
assert(head == nullptr);
std::vector<int> result;
LL_CopyDataToStdVector(nonFibonaciNodes, result);
assert(testArr == result);
LL_Delete(&nonFibonaciNodes);
}
{
std::vector<int> testArr = { 0, 4, 1, 6, 1, 7, 2, 9, 3, 10, 5, 8 };
std::vector<int> fibonaciArr = { 0, 1, 1, 2, 3, 5, 8 };
std::vector<int> nonFibonaciArr = { 4, 6, 7, 9, 10 };
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
LinkedListElement<int>* fibonaciNodes = nullptr;
LinkedListElement<int>* nonFibonaciNodes = nullptr;
LL_SpiltLinkedList<int>(&head, &fibonaciNodes, &nonFibonaciNodes, IsFibonaciNumber);
assert(fibonaciNodes != nullptr);
assert(nonFibonaciNodes != nullptr);
assert(head == nullptr);
std::vector<int> fibonaciResult;
LL_CopyDataToStdVector(fibonaciNodes, fibonaciResult);
assert(fibonaciArr == fibonaciResult);
std::vector<int> nonFibonaciResult;
LL_CopyDataToStdVector(nonFibonaciNodes, nonFibonaciResult);
assert(nonFibonaciArr == nonFibonaciResult);
LL_Delete(&fibonaciNodes);
LL_Delete(&nonFibonaciNodes);
}
}
pair<ListNode*, ListNode*> partitionList(ListNode *head){
int fib = 1, fib2 = 1;
int count = 0;
ListNode *fibhead, *fp;
fibhead = fp = new ListNode(0);
ListNode *nfibhead, *nfp;
nfibhead = nfp = new ListNode(0);
while(head != NULL){
if(count == fib){
// add to fib list
fp->next = head;
fp = fp->next;
// calculate the next Fibonacci number
fib = fib + fib2;
fib2 = fib - fib2;
}
else{
// add to non-fib list
nfp->next = head;
nfp = nfp->next;
}
count++;
head = head->next;
}
fp = fibhead->next;
delete fibhead;
nfp = nfibhead->next;
delete nfibhead;
return {fp, nfp};
}
import java.util.Iterator;
import java.util.LinkedList;
public class LinkedlistFibannocci {
public static void main(String args[])
{
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(10);
list.add(23);
list.add(17);
list.add(9);
list.add(5);
list.add(1);
list.add(34);
list.add(21);
seperateLinkedlist(list);
}
public static void seperateLinkedlist(LinkedList<Integer> list)
{
int number ;
if(list == null)
{
return;
}
LinkedList<Integer> fibseries = new LinkedList<Integer>();
LinkedList<Integer> nonfibseries = new LinkedList<Integer>();
Iterator<Integer> iter = list.iterator();
while(iter.hasNext())
{
number = iter.next();
if(isFibannoci(number))
fibseries.add(number);
else
nonfibseries.add(number);
}
System.out.println(" Fibannocci linkedlist"+fibseries);
System.out.println(" non- Fibannocci linkedlist"+nonfibseries);
}
private static boolean isFibannoci(int number) {
int a=0,b=1,c=0;
if(number < 0)
throw new IllegalArgumentException();
while(c<number)
{
c=a+b;
a=b;
b=c;
}
if(c==number)
return true;
else
return false;
}
}
import java.util.Iterator;
import java.util.LinkedList;
public class LinkedlistFibannocci {
public static void main(String args[])
{
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(10);
list.add(23);
list.add(17);
list.add(9);
list.add(5);
list.add(1);
list.add(34);
list.add(21);
seperateLinkedlist(list);
}
public static void seperateLinkedlist(LinkedList<Integer> list)
{
int number ;
if(list == null)
{
return;
}
LinkedList<Integer> fibseries = new LinkedList<Integer>();
LinkedList<Integer> nonfibseries = new LinkedList<Integer>();
Iterator<Integer> iter = list.iterator();
while(iter.hasNext())
{
number = iter.next();
if(isFibannoci(number))
fibseries.add(number);
else
nonfibseries.add(number);
}
System.out.println(" Fibannocci linkedlist"+fibseries);
System.out.println(" non- Fibannocci linkedlist"+nonfibseries);
}
private static boolean isFibannoci(int number) {
int a=0,b=1,c=0;
if(number < 0)
throw new IllegalArgumentException();
while(c<number)
{
c=a+b;
a=b;
b=c;
}
if(c==number)
return true;
else
return false;
}
}
#include<iostream>
using namespace std;
struct node
{
int data;
struct node* next;
};
void pop_list(struct node* start)
{
int x = 13, i=0;
while(i++<20)
{
start->data = x;
start->next = new node;
start = start->next;
x = x + 1;
}
x = 12;
while(i++<30)
{
start->data = x;
start->next = new node;
start = start->next;
x = x - 1;
}
start->data=2;
start->next=NULL;
}
void print_list(struct node* start)
{
while(start)
{
cout << start->data << " ";
start=start->next;
}
cout << endl;
}
bool if_fibonicci(int n)
{
int f1=1,f2=1,f=1;
while(f<n)
{
f=f1+f2;
f1=f2;
f2=f;
}
if(f == n)
return true;
else
return false;
}
int main()
{
struct node* start = new node,*temp,*fibo_series=NULL, *non_fibo_series=NULL;
pop_list(start);
print_list(start);
temp=start;
while(temp)
{
if(if_fibonicci(temp->data))
{
if(!fibo_series)
{
fibo_series = new node;
fibo_series->data = temp->data;
fibo_series->next = NULL;
}
else
{
struct node* t = fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
else
{
if(!non_fibo_series)
{
non_fibo_series = new node;
non_fibo_series->data = temp->data;
non_fibo_series->next = NULL;
}
else
{
struct node* t = non_fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
temp=temp->next;
}
cout << " fibonacci series " << endl;
print_list(fibo_series);
cout << " NON fibonacci series " << endl;
print_list(non_fibo_series);
return 0;
}
// Given a linked list, convert into 2 linked lists such that one contains fibonacci numbers other non fibonacci numbers
#include<iostream>
#include<string>
using namespace std;
struct node
{
int data;
struct node* next;
};
void print_list(struct node* start)
{
while(start)
{
cout << start->data << " ";
start=start->next;
}
cout << endl;
}
void pop_list(struct node* start)
{
int x = 13, i=0;
while(i++<20)
{
start->data = x;
start->next = new node;
start = start->next;
x = x + 1;
}
x = 12;
while(i++<30)
{
start->data = x;
start->next = new node;
start = start->next;
x = x - 1;
}
start->data=2;
start->next=NULL;
}
bool if_fibonicci(int n)
{
int f1=1,f2=1,f=1;
while(f<n)
{
f=f1+f2;
f1=f2;
f2=f;
}
if(f == n)
return true;
else
return false;
}
int main()
{
struct node* start = new node,*temp,*fibo_series=NULL, *non_fibo_series=NULL;
pop_list(start);
print_list(start);
temp=start;
while(temp)
{
if(if_fibonicci(temp->data))
{
//cout << " Number belongs to fibonacci series " << endl;
if(!fibo_series)
{
fibo_series = new node;
fibo_series->data = temp->data;
fibo_series->next = NULL;
}
else
{
struct node* t = fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
else
{
//cout << " Number DOESNOT belongs to fibonacci series " << endl;
if(!non_fibo_series)
{
non_fibo_series = new node;
non_fibo_series->data = temp->data;
non_fibo_series->next = NULL;
}
else
{
struct node* t = non_fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
temp=temp->next;
}
cout << " fibonacci series " << endl;
print_list(fibo_series);
cout << " NON fibonacci series " << endl;
print_list(non_fibo_series);
return 0;
}
// Given a linked list, convert into 2 linked lists such that one contains fibonacci numbers other non fibonacci numbers
#include<iostream>
#include<string>
using namespace std;
struct node
{
int data;
struct node* next;
};
void print_list(struct node* start)
{
while(start)
{
cout << start->data << " ";
start=start->next;
}
cout << endl;
}
void pop_list(struct node* start)
{
int x = 13, i=0;
while(i++<20)
{
start->data = x;
start->next = new node;
start = start->next;
x = x + 1;
}
x = 12;
while(i++<30)
{
start->data = x;
start->next = new node;
start = start->next;
x = x - 1;
}
start->data=2;
start->next=NULL;
}
bool if_fibonicci(int n)
{
int f1=1,f2=1,f=1;
while(f<n)
{
f=f1+f2;
f1=f2;
f2=f;
}
if(f == n)
return true;
else
return false;
}
int main()
{
struct node* start = new node,*temp,*fibo_series=NULL, *non_fibo_series=NULL;
pop_list(start);
print_list(start);
temp=start;
while(temp)
{
if(if_fibonicci(temp->data))
{
//cout << " Number belongs to fibonacci series " << endl;
if(!fibo_series)
{
fibo_series = new node;
fibo_series->data = temp->data;
fibo_series->next = NULL;
}
else
{
struct node* t = fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
else
{
//cout << " Number DOESNOT belongs to fibonacci series " << endl;
if(!non_fibo_series)
{
non_fibo_series = new node;
non_fibo_series->data = temp->data;
non_fibo_series->next = NULL;
}
else
{
struct node* t = non_fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
temp=temp->next;
}
cout << " fibonacci series " << endl;
print_list(fibo_series);
cout << " NON fibonacci series " << endl;
print_list(non_fibo_series);
return 0;
}
// Given a linked list, convert into 2 linked lists such that one contains fibonacci numbers other non fibonacci numbers
#include<iostream>
#include<string>
using namespace std;
struct node
{
int data;
struct node* next;
};
void print_list(struct node* start)
{
while(start)
{
cout << start->data << " ";
start=start->next;
}
cout << endl;
}
void pop_list(struct node* start)
{
int x = 13, i=0;
while(i++<20)
{
start->data = x;
start->next = new node;
start = start->next;
x = x + 1;
}
x = 12;
while(i++<30)
{
start->data = x;
start->next = new node;
start = start->next;
x = x - 1;
}
start->data=2;
start->next=NULL;
}
bool if_fibonicci(int n)
{
int f1=1,f2=1,f=1;
while(f<n)
{
f=f1+f2;
f1=f2;
f2=f;
}
if(f == n)
return true;
else
return false;
}
int main()
{
struct node* start = new node,*temp,*fibo_series=NULL, *non_fibo_series=NULL;
pop_list(start);
print_list(start);
temp=start;
while(temp)
{
if(if_fibonicci(temp->data))
{
//cout << " Number belongs to fibonacci series " << endl;
if(!fibo_series)
{
fibo_series = new node;
fibo_series->data = temp->data;
fibo_series->next = NULL;
}
else
{
struct node* t = fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
else
{
//cout << " Number DOESNOT belongs to fibonacci series " << endl;
if(!non_fibo_series)
{
non_fibo_series = new node;
non_fibo_series->data = temp->data;
non_fibo_series->next = NULL;
}
else
{
struct node* t = non_fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
temp=temp->next;
}
cout << " fibonacci series " << endl;
print_list(fibo_series);
cout << " NON fibonacci series " << endl;
print_list(non_fibo_series);
return 0;
}
In this case I did not remember how compute if number is Fibonacci so what I do is:
- get max element in the list
- compute fibonacci numbers up to that element and store in set
- go through the list. if element is in the set add it to fibnacci list otherwise add it to non-fibonacci list:
#include <iostream>
#include <list>
#include <set>
using namespace std;
int getMaxValue(const list<int> &l) {
int max = 0;
for (list<int>::const_iterator it=l.begin();it!=l.end();++it)
if ((*it) > max)
max = *it;
return max;
}
set<int> getFibonacciNumbers(int limit) {
set<int> fibonacci;
int result = 0;
int number1 = 0;
int number2 = 1;
while(result < limit) {
result = number1 + number2;
number2 = number1;
number1 = result;
fibonacci.insert(result);
}
return fibonacci;
}
int main() {
list<int>isFibonacci;
list<int>isNotFibonacci;
list<int>mylist;
mylist.push_back(1);
mylist.push_back(5);
mylist.push_back(20);
mylist.push_back(7);
mylist.push_back(13);
mylist.push_back(56);
set<int> fibonacciNumbers = getFibonacciNumbers(getMaxValue(mylist));
for (list<int>::iterator it=mylist.begin();it!=mylist.end();++it)
if(fibonacciNumbers.find(*it) != fibonacciNumbers.end())
isFibonacci.push_back(*it);
else
isNotFibonacci.push_back(*it);
cout << "Fibonacci numbers: " << endl;
for (list<int>::iterator it=isFibonacci.begin();it!=isFibonacci.end();++it)
cout << *it << " ";
cout << endl;
cout << "No Fibonacci numbers: " << endl;
for (list<int>::iterator it=isNotFibonacci.begin();it!=isNotFibonacci.end();++it)
cout << *it << " ";
return 0;
}
In my case I did not remember how to calculate if number is fibonacci so I have used different algorithm:
- Get max element in the list
- Compute fibonacci sequence up to that max element and store it in set
- Go through the list and check if each element is in the set, if it is add it to fibonacci list, add it to non-fibonacci list otherwise
#include <iostream>
#include <list>
#include <set>
using namespace std;
int getMaxValue(const list<int> &l) {
int max = 0;
for (list<int>::const_iterator it=l.begin();it!=l.end();++it)
if ((*it) > max)
max = *it;
return max;
}
set<int> getFibonacciNumbers(int limit) {
set<int> fibonacci;
int result = 0;
int number1 = 0;
int number2 = 1;
while(result < limit) {
result = number1 + number2;
number2 = number1;
number1 = result;
fibonacci.insert(result);
}
return fibonacci;
}
int main() {
list<int>isFibonacci;
list<int>isNotFibonacci;
list<int>mylist;
mylist.push_back(1);
mylist.push_back(5);
mylist.push_back(20);
mylist.push_back(7);
mylist.push_back(13);
mylist.push_back(56);
set<int> fibonacciNumbers = getFibonacciNumbers(getMaxValue(mylist));
for (list<int>::iterator it=mylist.begin();it!=mylist.end();++it)
if(fibonacciNumbers.find(*it) != fibonacciNumbers.end())
isFibonacci.push_back(*it);
else
isNotFibonacci.push_back(*it);
cout << "Fibonacci numbers: " << endl;
for (list<int>::iterator it=isFibonacci.begin();it!=isFibonacci.end();++it)
cout << *it << " ";
cout << endl;
cout << "No Fibonacci numbers: " << endl;
for (list<int>::iterator it=isNotFibonacci.begin();it!=isNotFibonacci.end();++it)
cout << *it << " ";
return 0;
}
In my case I did not remember how to calculate if number is fibonacci so I have used different algorithm:
- Get max element in the list
- Compute fibonacci sequence up to that max element and store it in set
- Go through the list and check if each element is in the set, if it is add it to fibonacci list, add it to non-fibonacci list otherwise
#include <iostream>
#include <list>
#include <set>
using namespace std;
int getMaxValue(const list<int> &l) {
int max = 0;
for (list<int>::const_iterator it=l.begin();it!=l.end();++it)
if ((*it) > max)
max = *it;
return max;
}
set<int> getFibonacciNumbers(int limit) {
set<int> fibonacci;
int result = 0;
int number1 = 0;
int number2 = 1;
while(result < limit) {
result = number1 + number2;
number2 = number1;
number1 = result;
fibonacci.insert(result);
}
return fibonacci;
}
int main() {
list<int>isFibonacci;
list<int>isNotFibonacci;
list<int>mylist;
mylist.push_back(1);
mylist.push_back(5);
mylist.push_back(20);
mylist.push_back(7);
mylist.push_back(13);
mylist.push_back(56);
set<int> fibonacciNumbers = getFibonacciNumbers(getMaxValue(mylist));
for (list<int>::iterator it=mylist.begin();it!=mylist.end();++it)
if(fibonacciNumbers.find(*it) != fibonacciNumbers.end())
isFibonacci.push_back(*it);
else
isNotFibonacci.push_back(*it);
cout << "Fibonacci numbers: " << endl;
for (list<int>::iterator it=isFibonacci.begin();it!=isFibonacci.end();++it)
cout << *it << " ";
cout << endl;
cout << "No Fibonacci numbers: " << endl;
for (list<int>::iterator it=isNotFibonacci.begin();it!=isNotFibonacci.end();++it)
cout << *it << " ";
return 0;
}
In my case I did not remember how to calculate if number is fibonacci so I have used different algorithm:
- Get max element in the list
- Compute fibonacci sequence up to that max element and store it in set
- Go through the list and check if each element is in the set, if it is add it to fibonacci list, add it to non-fibonacci list otherwise
#include <iostream>
#include <list>
#include <set>
using namespace std;
int getMaxValue(const list<int> &l) {
int max = 0;
for (list<int>::const_iterator it=l.begin();it!=l.end();++it)
if ((*it) > max)
max = *it;
return max;
}
set<int> getFibonacciNumbers(int limit) {
set<int> fibonacci;
int result = 0;
int number1 = 0;
int number2 = 1;
while(result < limit) {
result = number1 + number2;
number2 = number1;
number1 = result;
fibonacci.insert(result);
}
return fibonacci;
}
int main() {
list<int>isFibonacci;
list<int>isNotFibonacci;
list<int>mylist;
mylist.push_back(1);
mylist.push_back(5);
mylist.push_back(20);
mylist.push_back(7);
mylist.push_back(13);
mylist.push_back(56);
set<int> fibonacciNumbers = getFibonacciNumbers(getMaxValue(mylist));
for (list<int>::iterator it=mylist.begin();it!=mylist.end();++it)
if(fibonacciNumbers.find(*it) != fibonacciNumbers.end())
isFibonacci.push_back(*it);
else
isNotFibonacci.push_back(*it);
cout << "Fibonacci numbers: " << endl;
for (list<int>::iterator it=isFibonacci.begin();it!=isFibonacci.end();++it)
cout << *it << " ";
cout << endl;
cout << "No Fibonacci numbers: " << endl;
for (list<int>::iterator it=isNotFibonacci.begin();it!=isNotFibonacci.end();++it)
cout << *it << " ";
return 0;
}
In my case I did not remember how to calculate if number is fibonacci so I have used different algorithm:
- Get max element in the list
- Compute fibonacci sequence up to that max element and store it in set
- Go through the list and check if each element is in the set, if it is add it to fibonacci list, add it to non-fibonacci list otherwise
c++, implementation
- kyduke October 24, 2015struct Node { int val; Node* next; Node(int v) : next(NULL) { val = v; } }; bool isFibonacci(int n) { int k, r; k = n * n * 5 - 4; r = sqrt((double)k); if (r * r == k) return true; k = n * n * 5 + 4; r = sqrt((double)k); if (r * r == k) return true; return false; } void divideLinkedList(Node* node, Node** fRoot, Node** oRoot) { Node* fNode = NULL; Node* oNode = NULL; while (node) { if (isFibonacci(node->val) == true) { if (fNode == NULL) { *fRoot = node; fNode = *fRoot; } else { fNode->next = node; fNode = fNode->next; } } else { if (oNode == NULL) { *oRoot = node; oNode = *oRoot; } else { oNode->next = node; oNode = oNode->next; } } node = node->next; } if (fNode) fNode->next = NULL; if (oNode) oNode->next = NULL; }