## Yahoo Interview Question

Software Engineer / Developers**Country:**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;
}
```

- sergey.v.zimin November 02, 2017