Microsoft Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
public class MergeLists {
Node root;
Node root2;
class Node{
int data;
private Node next;
public Node(int data) {
this.data=data;
}
}
public void buildFirstList() {
root=new Node(1);
Node n1=new Node(2);
root.next=n1;
Node n2=new Node(3);
n1.next=n2;
Node n3=new Node(4);
n2.next=n3;
}
public void buildSecondList() {
root2=new Node(10);
Node n1=new Node(20);
root2.next=n1;
Node n2=new Node(30);
n1.next=n2;
Node n3=new Node(40);
n2.next=n3;
}
public void traverseAlt(Node n,Node n2) {
n=root;
n2=root2;
while(n!=null && n2!=null) {
System.out.println(n.data);
System.out.println(n2.data);
n=n.next;
n2=n2.next;
}
if(n==null && n2!=null) {
return;
}
else if(n2==null && n!=null){
return;
}
}
public void traverse(Node n) {
while(n!=null) {
System.out.println(n.data);
n=n.next;
}
}
public static void main(String args[]) {
MergeLists ml=new MergeLists();
ml.buildFirstList();
ml.buildSecondList();
ml.traverseAlt(ml.root, ml.root2);
//ml.traverse(ml.root2);
}
}
public static ListNode interLeaveLL(ListNode l1, ListNode l2){
ListNode head = new ListNode(0);
ListNode tmp = head;
boolean flag = true;
while (l1 != null && l2 != null){
if(flag){
tmp.next = l1;
tmp = tmp.next;
l1 = l1.next;
} else {
tmp.next = l2;
tmp = tmp.next;
l2 = l2.next;
}
flag = !flag;
}
while (l1 != null){
tmp.next = l1;
tmp = tmp.next;
l1 = l1.next;
}
return head.next;
}
public static ListNode interLeaveLL(ListNode l1, ListNode l2){
ListNode head = new ListNode(0);
ListNode tmp = head;
boolean flag = true;
while (l1 != null && l2 != null){
if(flag){
tmp.next = l1;
tmp = tmp.next;
l1 = l1.next;
} else {
tmp.next = l2;
tmp = tmp.next;
l2 = l2.next;
}
flag = !flag;
}
while (l1 != null){
tmp.next = l1;
tmp = tmp.next;
l1 = l1.next;
}
return head.next;
}
Fairly straightforward problem. The only clarification we might need is if to include the second LL's element in the last interleaving (i.e whether to include 40) but going by your example, it doesn't seem to be the case. This solution is expressed in Python below.
Solution:
Test code:
- prudent_programmer March 22, 2018