Yahoo Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
public static void main(String[] args) {
Node N5 = new Node(5, null);
Node N4 = new Node(4, N5);
Node N3 = new Node(3, N4);
Node N2 = new Node(2, N3);
Node N1 = new Node(1, N2);
separate(N1);
System.out.println("----------------");
Node N50 = new Node(5, null);
Node N40 = new Node(4, null);
Node N30 = new Node(3, N50);
Node N20 = new Node(2, N40);
Node N10 = new Node(1, N30);
merge(N10, N20);
}
// 1->3->5
// 2->4
public static void merge(Node n1, Node n2) {
Node node = null;
Node head = null;
while (n1 != null && n2 != null) {
if (node == null) {
node = new Node(n1.val, null);
head = node;
} else {
node.next = new Node(n1.val, null);;
node = node.next;
}
node.next = n2;
node = node.next;
n1 = n1.next;
n2 = n2.next;
}
if (n1 != null) {
node.next = n1;
node = node.next;
}
if (n2 != null) {
node.next = n2;
node = node.next;
}
node.next = null;
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
}
// 1->2->3->4->5
public static void separate(Node node) {
Node nodeE = null;
Node nodeO = null;
Node nhE = null;
Node nhO = null;
int i = 1;
while (node != null) {
if (i % 2 == 0) {
if (nodeE == null) {
nodeE = node;
nhE = nodeE;
} else {
nodeE.next = node;
nodeE = nodeE.next;
}
node = node.next;
} else {
if (nodeO == null) {
nodeO = node;
nhO = nodeO;
} else {
nodeO.next = node;
nodeO = nodeO.next;
}
node = node.next;
}
i++;
}
nodeE.next = null;
nodeO.next = null;
while (nhE != null) {
System.out.print(nhE.val + " ");
nhE = nhE.next;
}
System.out.println();
while (nhO != null) {
System.out.print(nhO.val + " ");
nhO = nhO.next;
}
}
static class Node {
int val;
Node next;
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
}
#include<iostream>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
next_ = NULL;
}
int val_;
Node *next_;
};
pair<Node *, Node *> Separate(Node *head)
{
Node *head2 = head ? head->next_ : NULL;
Node *n1 = head;
Node *n2 = head2;
while (n1 &&
n2)
{
Node *next_n1 = n2->next_;
Node *next_n2 = n2->next_ ? n2->next_->next_ : NULL;
n1->next_ = n2->next_;
n2->next_ = next_n2;
n1 = next_n1;
n2 = next_n2;
}
return pair<Node*, Node*>(head, head2);
}
Node *Merge(Node *head1, Node *head2)
{
Node *n1 = head1;
Node *n2 = head2;
while (n1 &&
n2)
{
Node *next_n1 = n1->next_;
Node *next_n2 = n2->next_;
n1->next_ = n2;
if (next_n1) {
n2->next_ = next_n1;
}
n1 = next_n1;
n2 = next_n2;
}
return head1;
}
void Print(Node *n) {
while (n) {
cout << n->val_ << "->";
n = n->next_;
}
cout << "\n";
}
int main()
{
Node n1(1), n2(2), n3(3), n4(4), n5(5);
n1.next_ = &n2;
n2.next_ = &n3;
n3.next_ = &n4;
n4.next_ = &n5;
pair<Node *, Node *> out = Separate(&n1);
Print(out.first);
Print(out.second);
Node *head = Merge(out.first, out.second);
Print(head);
return 0;
}
package Basics;
class Node {
int data;
Node next;
Node(int data, Node next){
this.data = data;
this.next = next;
}
}
class Test {
public static void main(String args[]) {
Test tt = new Test();
int i = 2;
Node t = new Node(1,null);
Node x = t;
while(i<6){
x.next = new Node(i,null);
x = x.next;
i++;
}
tt.seperator(t);
}
void printList(Node n){
while(n!=null){
System.out.print(n.data+" ");
n=n.next;
}
System.out.println();
}
void seperator(Node root){
boolean flag =false;
Node temp1=null,t1=null;
Node temp2=null,t2=null;
while(root!=null){
if(flag){
if(t2!=null){
t2.next = new Node(root.data,null);
t2 = t2.next;
}else{
temp2 = new Node(root.data,null);
t2 = temp2;
}
root = root.next;
flag = false;
}else{
if(t1!=null){
t1.next = new Node(root.data,null);
t1 = t1.next;
}else{
temp1 = new Node(root.data,null);
t1 = temp1;
}
root = root.next;
flag=true;
}
}
printList(temp1);
printList(temp2);
merger(temp1,temp2);
}
void merger(Node t1, Node t2){
Node root = null,head=null;
while(t1!=null && t2!=null){
if(t1.data<t2.data){
if(root!=null){
root.next = new Node(t1.data, null);
root = root.next;
}else{
root = new Node(t1.data,null);
head = root;
}
t1 = t1.next;
}else{
if(root!=null){
root.next = new Node(t2.data, null);
root = root.next;
}else{
root = new Node(t2.data,null);
head = root;
}
t2 = t2.next;
}
}
if(t1==null){
while(t2!=null){
root.next = new Node(t2.data, null);
root = root.next;
t2 = t2.next;
}
}
if(t2==null){
while(t1!=null){
root.next = new Node(t1.data, null);
root = root.next;
t1 = t1.next;
}
}
printList(head);
}
}
- sergey.v.zimin November 02, 2017