Microsoft Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

struct Node *MergeOnebyOne(struct Node *a,struct Node *b)
{
if(!a)
return b;
if(!b)
return a;
struct Node *head=a,*res=a,*prev=NULL;
while(a && b)
{
struct Node *t=a->next;
struct Node *q=b->next;
res->next=b;
res=res->next;
res->next=t;
prev=res;
res=res->next;
a=t;
b=q;
}
if(a)
prev->next=a;
else if(b)
prev->next=b;
return head;
}

- Anonymous January 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Test Cases:
1: Both link list has same length.
2. 1st link length >2nd link list length
3: 1st link length >2nd link list length
4: Both link list are NULL
5. 1st link list is NULL
6. 2nd link list is NULL
I think all the test cases are handle in above solution

- Anonymous January 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can a link have loop?
can the two list me merging linked list, like Y?

- Anonymous February 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

Look at below method in java. This method accept 2 areguments, both are first node of two different list which we want to merge one by one. Any suggestion is appreciated.

public ListNode mergeOneByOne(ListNode node1, ListNode node2) {
		ListNode node1Next = null, node2Next = null, head = null;
		if (node1 != null && node2 != null) {
			head = node1;
			while (node1 != null && node2 != null) {
				if (node1.next == null && node2.next == null) {
					node1.next = node2;
					break;
				}
				node1Next = node1.next;
				node2Next = node2.next;
				if (node1Next == null && node2Next != null) {
					node1Next = node2Next;
					node1.next = node2;
					node2.next = node1Next;
					break;
				}
				node1.next = node2;
				node2.next = node1Next;
				node1 = node1Next;
				node2 = node2Next;
			}
		}
		return head;
	}

- Geet February 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Doesn't work for lists of uneven length.

list1: 1 - 3 - 5 - 7 - 8
list2: 2 - 4

Exits after list2 completes 4.

- jtgi March 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@jtgi I updated my code. try it

- Geet March 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

what if lists are like this
1->2
3->4->5

You need to update node1 and node 2 in second if block in while loop.

- jeetsahu March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

public static void joinLL(LL ll1,LL ll2){
		joinLL(ll1.first,ll2.first);
}
public static void joinLL(Node first1,Node first2){
		if(first1==null || first2==null)return;
		Node temp1=first1.next;
		Node temp2=first2.next;
		first1.next=first2;
		if(temp1!=null)first2.next=temp1;
		joinLL(temp1,temp2);	
}

- Karthik Vvs January 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

do we really need the recursion for such a simple task? the iterative approach is pretty trivial to implement.

- S.Abakumoff January 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

iteration or recursion can be used as long as the time complexity of the problem doesn't change..its also not hard to implement recursion ...

- Karthik Vvs January 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Did any one think about the test cases for this question?

- Ravi Vooda January 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Maybe where one linkedlist is much shorter than the other, one of the linkedlists is null, the two linkedlists are of different types

- Anonymous February 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Maybe where one linkedlist is much shorter than the other, one of the linkedlists is null, the two linkedlists are of different types

- Anonymous February 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

start = a = firstList;
b = a->next; 
c = secondList;
d = c->next;
while(firstList ->next != NULL && a!=NULL && b!=NULL && c!=NULL)
{
a->next = c;
c->next = b;
a = b;
c = d;
b = b->next; 
d = d == NULL? NULL: d->next;
firstList = firstList->next ->next;
}
PrintResult(start);

Test cases should be
1. Check the resultant linkedlist length = length(firstlist) + length(secondlist).
2. Every position * 2 th (starting from position = 1) element in the resultant list should be in second list.
3. Every pos*2 th element in the resultant list should be in second list in a sequence.
4. Every element in odd position in the resultant list should be in first list.
5. Every element in odd position in the resultant list should be in first list in a sequence.

- Spandy January 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you give some recursive aproach?

- pl March 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

_linkList* combine(_linkList* head1, _linkList* head2)
{
if(head1 == NULL && head2 == NULL)
return NULL;
if(head1 == NULL)
return head2;
else if(head2 == NULL)
return head1;

_linkList* curr1 = head1->next;
_linkList* curr2 = head2->next;
head1->next = head2;
head2->next = combine(curr1, curr2);
return head1;
}

- kimi February 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class CombineTwoList {
public static LinkedList<Integer> CombineList(LinkedList<Integer> l1,
LinkedList<Integer> l2) {
if (l1.isEmpty() && l2.isEmpty()) {
return null;
}
if (l1.isEmpty())
return l2;
if (l2.isEmpty())
return l1;

int FirstListLength = l1.size();
int SecondListLength = l2.size();
if (l1.size() < l2.size()) {
for (int i = 0; i < FirstListLength; i++) {
Integer tempInt = (Integer) l1.remove(0);
l2.add((i + i + 1), tempInt);
}
return l2;
} else {
for (int i = 0; i < SecondListLength; i++) {
Integer tempInt = (Integer) l2.remove(0);

l1.add((i + i + 1), tempInt);
}
return l1;
}

}

public static void main(String[] args) {
LinkedList<Integer> list1 = new LinkedList<Integer>();
LinkedList<Integer> list2 = new LinkedList<Integer>();
list1.add(1);
list1.add(2);
list1.add(3);
list1.add(4);
list2.add(5);
list2.add(6);
list2.add(7);
LinkedList<Integer> output = CombineList(list1, list2);

}

}

- Anonymous February 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here what I came up with the solution and test cases so far...Assuming I have two lists list1 and list2
Code..
{
Node curr1 = list1.head;
Node curr2 = list2.head;
if (curr1 == null || curr2 == null) //Checking if any of the list is empty
return;
//Counting the nodes or lenght of both the lists

while (curr1 != null)
{
count1++;
curr1 = curr1.next;
}
while (curr2 != null)
{
count2++;
curr2 = curr2.next;
}
//Logic of joining is to create a new node and appned in the middle of two elements of list1. The data in the new node is coming from List2. That way adding elemts of list2 alternatively in the middle of two elemnts of list1
if (count1 < count2 || count1 == count2)
count = count1 - 1;
else
count = count2;
curr1 = list1.head;
curr2 = list2.head;
while (count != 0)
{
{
Node newnode = new Node();
newnode.data = curr2.data;
newnode.next = curr1.next;
curr1.next = newnode;
curr1 = curr1.next.next;
curr2 = curr2.next;
}
count--;
}
if (count1 < count2 || count1 == count2) //If List1 is smaller than list2 then appending the remaining nodes of list2 to the last elemnt of list1.
curr1.next = curr2;

curr1 = list1.head;
Console.WriteLine("Conected list is:");
while (curr1 != null)
{
Console.WriteLine(curr1.data);
curr1 = curr1.next;
}
/*
* TEST CASES
* 1 What if both lists are empty or any one lost is empty
* Is it joining the lists with alternative elements
* Is it handling the situation where 1 list is smaller than the other.
* It is working if both the lists are of same length.
* Whats the complexity?
* */
}

- Suvi February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Optimised solution...
while (curr1 != null)
{
count1++;
curr1 = curr1.next;
}
while (curr2 != null)
{
count2++;
curr2 = curr2.next;
}
//Logic of joining is to create a new node and appned in the middle of two elements of list1. The data in the new node is coming from List2. That way adding elemts of list2 alternatively in the middle of two elemnts of list1
if (count1 < count2 || count1 == count2)
count = count1 - 1;
else
count = count2;
curr1 = list1.head;
curr2 = list2.head;
Node tempptr = new Node();
while (count != 0)
{
tempptr = curr2.next;
curr2.next = curr1.next;
curr1.next = curr2;
curr2 = tempptr;
curr1=curr1.next.next;
count--;
}
if (count1 < count2 || count1 == count2) //If List1 is smaller than list2 then appending the remaining nodes of list2 to the last elemnt of list1.
curr1.next = curr2;

- Suvi.. February 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

node* alternate(node* L1, node* L2) {
   if(L1 == null)
      return L2;
   else if(L2 == null)
      return L1;

   node* result = L1;

   while(L2) {
       node* t = L1->next;
       L1->next = L2;
       L2 = t;
       L1 = L1->next;
   }

   return result;
}

- iimanii February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good style

- 11mx31 May 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

L1->next could result in a null deref if the L1 list is shorter than the L2 list

- Anonymous April 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

node* join(node* head1, node* head2)
{
  node* temp1=head1;
  node* temp2=head2;

  while(temp1!=NULL&&temp2!=NULL)
  {

    head2=head2->next;

    temp2->next=temp1->next;
    temp1->next=temp2;
    temp1=temp2->next;

    if(temp2->next!=NULL)
     temp2=head2;
    else
     temp2->next=head2;

  }

  return head1!=NULL?head1:head2;

}

- Anonymous February 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;

public class CombineLinkedList {

	public static LinkedList<Integer> combine(LinkedList<Integer> l1,
			LinkedList<Integer> l2) {
		if (l1 == null && l2 == null) {
			return null;
		} else if (l1 == null) {
			return l2;
		} else if (l2 == null) {
			return l1;
		}
		// handle common cases
		LinkedList<Integer> result = new LinkedList<Integer>();
		int size1 = l1.size();
		int size2 = l2.size();
		int size = size1 < size2 ? size1 : size2;
		for (int i = 0; i < size; i++) {
			result.add(l1.get(i));
			result.add(l2.get(i));
		}
		if (size1 < size2) {
			for (int i = size1; i < size2; i++) {
				result.add(l2.get(i));
			}
		} else if (size1 > size2) {
			for (int i = size2; i < size1; i++) {
				result.add(l1.get(i));
			}
		} else {
			;
		}
		return result;
	}

	public static void main(String[] args) {
		LinkedList<Integer> list1 = new LinkedList<Integer>();
		list1.add(1);
		list1.add(2);
		list1.add(3);
		list1.add(4);
		LinkedList<Integer> list2 = new LinkedList<Integer>();
		list2.add(5);
		list2.add(6);
		list2.add(7);
		LinkedList<Integer> list = combine(list1, list2);
		System.out.println(list);
	}

}

- Kevin February 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is solution in C#.net
public MyNode MergeOneByOne(MyNode node1, MyNode node2)
{

MyNode cur, head;
if (node1 != null && node2 != null)
{
cur = head = node1;
node1 = node1.next;
}
else
return null;
while (node1 != null || node2 != null)
{
if (node2 != null)
{
cur = cur.next = node2;
node2 = node2.next;
}
if (node1 != null)
{
cur = cur.next = node1;
node1 = node1.next;
}
}
return head;
}

- Phani Krishna March 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//If Both Node are in same size
Node *MergeOnebyOne(Node *n1,Node *n2)
{
Node *res = new Node;
if(n1 != NULL)
{
res = new Node();
res->data = n1->data;
res->next = NULL;
}
if(n2 != NULL)
{
Node * tmp = new Node;
tmp->data = n2->data;
tmp->next = NULL;
res->next = tmp;

}
if((n1->next != NULL) && (n2->next != NULL))
{
Node *more = MergeOnebyOne(n1->next,n2->next);
res->next->next = more;
}

return res;
}

- Arunkumar March 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this works for all cases, any suggestion will be appreciated.

public static ListNode mergeTwoLists(ListNode head1, ListNode head2)
	{	
		ListNode head = new ListNode(0);
		ListNode current = head;
		
		while (head1!=null && head2!=null)
		{
			current.next = head1;
			current = current.next;
			head1 = head1.next;
			
			current.next = head2;
			current = current.next;
			head2 = head2.next;	
		}
		
		if (head1 != null)
			current.next = head1;
		else
			current.next = head2;
		
		return head.next;	
	}

- Jason_Weng March 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node* alternate(Node* p,Node* q)
{
int flag1=flag2=1;
if(p == NULL)
return q;
if(q == NULL)
return p;
node *head,*p1,*p2;
p1 = p;
p2 = q;
while(p1 != NULL && p2 != NULL)
{
if(flag1)
{
head->next = p1;
p1= p1->next;
flag1 = 0;
flag2 =1;
}

if(flag2)
{
head->next = p2;
p2 = p2->next;
falg2 = 0;
flag1 =1;
}

}
//when one of them go to the end ,flag1 = flag2 =0
if(flag1 == 0 && flag2 ==0)
{
if(p1 != NULL)
head->next = p1;
if(q2 != NULL)
head->next = p2;
}
return head;
}

- vic April 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main(string[] args)
        {
            int[] a = new int[] {1,2,3,4 };
            Node root0 = CreateAList(a);

            int[] b = new int[] { 5, 6, 7 };
            Node root1 = CreateAList(b);

            Node c = CrossCombineTwoLinkList(root0, root1);
        }

        static Node CrossCombineTwoLinkList(Node a, Node b)
        {
            Node root = a;
            Node aPre = null;
            Node bPre = null;
            while (a != null & b != null)
            {
                aPre = a;
                a = a.Next;
                bPre = b;
                b = b.Next;

                aPre.Next = bPre;
                bPre.Next = a;
            }

            if (b != null)
            {
                aPre.Next = b;
            }

            return root;
        }

- jinzha May 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void merge_one_by_one(struct node* *start1,struct node* *start2){
	struct node *p=*start1,*q=*start2,*r,*s;
	while(p && q)
	{
		r=p->next;
		s=q->next;
		p->next=q;
		q->next=r;
		p=r;
		q=s;
		if(!p->next)
		{
			p->next=q;
			return;
		}
		p=p->next;
		q=q->next;
	}

}

- tejaravi38 June 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void MergeListAlternatively(stIntList* pList1,stIntList* pList2,stIntList*& pSorted)
{
bool bFirstIncremented = false;
stIntList* pTemp1 = pList1;
stIntList* pTemp2 = pList2;
stIntList* pCurr = NULL;
while(pTemp1 != NULL || pTemp2 != NULL)
{
if(!bFirstIncremented)
{
if(pTemp1 != NULL)
{
if(pSorted == NULL)
{
pSorted = new stIntList;
pSorted->data = pTemp1->data;
pSorted->pNList = NULL;
pCurr = pSorted;
}
else
{
stIntList* pNew = new stIntList;
pNew->data = pTemp1->data;
pNew->pNList = NULL;
stIntList* pTemp = pCurr;
pTemp->pNList = pNew;
pCurr = pNew;
}
pTemp1 = pTemp1->pNList;
}
bFirstIncremented = true;
}
if(bFirstIncremented)
{
if(pTemp2 != NULL)
{
stIntList* pNew = new stIntList;
pNew->data = pTemp2->data;
pNew->pNList = NULL;
stIntList* pTemp = pCurr;
pTemp->pNList = pNew;
pCurr = pNew;
bFirstIncremented = false;
pTemp2 = pTemp2->pNList;
}
bFirstIncremented = false;
}
}
}

- rishikantku June 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this?

While end of second list is not reached just insert
Each node from second between two noded of first list.

- Anonymous July 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void merge_lists(node*& head1, node*& head2)
{
	if(head1 == NULL)
	{
		head1 = head2;
		return;
	}

	if(head2 == NULL) return;

	node* ptr1 = head1, ptr2 = head2;
	while(ptr1->next != NULL && ptr2->next != NULL)
	{
		ptr2->next = ptr1->next;
		ptr1->next = ptr2;

		ptr1 = ptr1->next;
		ptr2 = ptr2->next
	}
}

This can also be done recursively but you have to be careful with the base cases. For test cases, I'd test for when the pointers are NULL and when either/both list has a single element.

- Anonymous July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Test Cases:
1) Both Linked List have same length.
2) First Linked List length < Second Linked List length
3) First Linked List length > Second Linked List length
4) Both Linked List are null
5) First Linked List is null
6) Second Linked List is null

Below is recursive solution to the problem. It can be solved iteratively as well, but recursive solution seems more cleaner.

public LinkedListNode<Integer> alternateAdd(LinkedListNode<Integer> list1, 
								LinkedListNode<Integer> list2){
		if(list1 == null){
			return list2;
		}else if(list2 == null){
			return list1;
		}else{
			list2.setNext(alternateAdd(list1.getNext(), list2.getNext()));
			list1.setNext(list2);
			return list1;
		}
	}

- Ketan Mehta September 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my stab at it:

list *merge(list **head_1, list **head_2)
{
        list *temp_1 = *head_1;
        list *temp_2 = *head_2;
        while (temp_1 && temp_2) {
                list *temp_1_next_backup, *temp_2_next_backup;
                temp_1_next_backup = temp_1->next;
                temp_1->next = temp_2;
                temp_2_next_backup = temp_2->next;
                temp_2->next = temp_1_next_backup;
                temp_1 = temp_2->next;
                temp_2 = temp_2_next_backup;
        }
        return *head_1;
}

- aka October 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
*
*/
package com.singlelinkedlist;

/**
* @author mohammed.anas
*
*/
public class SingleNode {

String data;
SingleNode nextnode;

public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public SingleNode getNextnode() {
return nextnode;
}
public void setNextnode(SingleNode nextnode) {
this.nextnode = nextnode;
}

public SingleNode(String data){

this.data=data;
this.nextnode=null;
}

}
******************************************************************
package com.singlelinkedlist;

public class SingleLinkedListSecond {

private SingleNode start;
private SingleNode end;
public SingleLinkedListSecond(){
this.start=null;
this.end=null;
}

public void insert(String data){

if(start==null){
start=new SingleNode(data);
end=start;
}
else{

end.nextnode=new SingleNode(data);
end=end.nextnode;

}
}

public SingleNode getStart() {
return start;
}

public void setStart(SingleNode start) {
this.start = start;
}

public SingleNode getEnd() {
return end;
}

public void setEnd(SingleNode end) {
this.end = end;
}


}
***************************************************************
/**
*
*/
package com.singlelinkedlist;

/**
* @author mohammed.anas
*
*/
public class SingleLinkedList {

/**
* @param args
*/
private SingleNode start;
private SingleNode end;
public SingleLinkedList(){
this.start=null;
this.end=null;
}

private void insert(String data){

if(start==null){
start=new SingleNode(data);
end=start;
}
else{

end.nextnode=new SingleNode(data);
end=end.nextnode;

}
}

private void delete(String data){
SingleNode next=start.nextnode;
SingleNode prev=start;
if(data==start.getData()){
start=start.nextnode;
}
else{
while(next.getData()!=data){
next=next.nextnode;
prev=prev.nextnode;
}
if(next==end){
prev.nextnode=null;
end=prev;
}
else{
prev.nextnode=next.nextnode;
}}

}
private void display(){
SingleNode temp=start;
while(temp!=null){
System.out.println(temp.getData());
temp=temp.nextnode;
}

}
private void display2(SingleLinkedListSecond node){
SingleNode temp=node.getStart();
while(temp!=null){
System.out.println(temp.getData());
temp=temp.nextnode;
}

}
private void merge(SingleNode node1,SingleNode node2){
SingleNode nxt1=null;
SingleNode nxt2=null;
if(node1==null&&node2==null){
return;
}
else if(node1!=null&&node2==null){
nxt1=node1.nextnode;
node1.nextnode=node2;
merge(nxt1,node2);
}
else if(node1==null&&node2!=null){
nxt2=node2.nextnode;
node2.nextnode=node1;
merge(node1,nxt2);
}
else{
nxt1=node1.nextnode;
node1.nextnode=node2;
nxt2=node2.nextnode;
node2.nextnode=nxt1;
merge(nxt1, nxt2);
}
}
private void reverse(){

SingleNode result=null;
SingleNode next;
while(start!=null){

next=start.nextnode;
start.nextnode=result;
result=start;
start=next;

}
start=result;


}


public static void main(String[] args) {

SingleLinkedList singleLinkedList=new SingleLinkedList();
singleLinkedList.insert("Germany");
singleLinkedList.insert("Poland");
singleLinkedList.insert("Russia");
singleLinkedList.insert("Japan");
singleLinkedList.insert("Turkey");
singleLinkedList.insert("Protugal");
singleLinkedList.display();
System.out.println("********************************");
SingleLinkedListSecond singleLinkedListSecond=new SingleLinkedListSecond();
singleLinkedListSecond.insert("Germany");
singleLinkedListSecond.insert("Poland");
singleLinkedListSecond.insert("Russia");
singleLinkedListSecond.insert("Japan");
singleLinkedListSecond.insert("Turkey");
singleLinkedListSecond.insert("Protugal");
singleLinkedList.display2(singleLinkedListSecond);
singleLinkedList.merge(singleLinkedList.start,singleLinkedListSecond.getStart());
System.out.println("******************************");
singleLinkedList.display();

}

}

- Mohammed Anas November 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void addAlternate(NumbersLL list1, NumbersLL list2) {

		NumbersLL newList = new NumbersLL();
		
		int size = list1.getNodeCount() + list2.getNodeCount();
		int i = 1, j = 1, k=1;
		while(i <= size){
			if(i % 2 == 1){
				newList.addData(list1.getNode(j));
				j++;
			}
			if(i % 2 == 0){
				newList.addData(list2.getNode(k));
				k++;
			}
			i++;
		}
		
		newList.printData();

	}

- Nayan August 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will not work for additional node is added to the any of the list. I will update the code and will post again.

- Nayan August 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is the java code to solve this problem.

class Nodecom{
	Nodecom next;
	int data;
	Nodecom(int x){
		data=x;
	}

}
public class CombineLists {

Nodecom root;
	
	public void print(){
		Nodecom temp =root;
		if(temp==null)
			return;
		while(temp!=null){
			System.out.print(temp.data+" ");
			temp=temp.next;
		}
	}
	public void combine(Nodecom root1, Nodecom root2){
		Nodecom l1=root1;
		Nodecom l2=root2;
		if(l1==null||l2==null){
			System.out.println("One of the nodes is empty");
			return;
		}
		while(l1.next!=null||l2.next!=null){
			Nodecom t1=l1.next;
			Nodecom t2=l2.next;
			l1.next=l2;
			l2.next=t1;
			l1=t1;
			l2=t2;
			
		}
		l1.next=l2;
		l2.next=null;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		CombineLists link =new CombineLists();
		link.root=new Nodecom(1);
		link.root.next=new Nodecom(2);
		link.root.next.next=new Nodecom(3);
		link.root.next.next.next=new Nodecom(4);
		link.root.next.next.next.next=new Nodecom(10);
		link.print();
		
		CombineLists link2 =new CombineLists();
		link2.root=new Nodecom(21);
		link2.root.next=new Nodecom(22);
		link2.root.next.next=new Nodecom(23);
		link2.root.next.next.next=new Nodecom(24);
		link2.root.next.next.next.next=new Nodecom(25);
		System.out.println("2nd list is");
		link2.print();
		link.combine(link.root, link2.root);
		System.out.println("Combined list is ");
		link.print();
	}

}

- RishabG June 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

When I was being interviewed by microsoft, the guy told me to give a 4 line recursive solution to above question, this was my solution.

Node* alternate(Node* p,Node* q){
if (p== NULL) return q;

else if(q==NULL) return p;

else{
Node* temp = alternate(q,p.next) ;
return temp;
}

}

- Ashish February 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you please explain how this works?

- abc March 22, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More