CareerCup

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;
}

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;
	}

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);	
}

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

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.

_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;
}

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);

}

}

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?
* */
}

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;
}

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;

}

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);
	}

}

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;
}

//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;
}

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;	
	}

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;
}

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;
        }

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;
	}

}

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;
}
}
}

How about this?

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

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.

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;
		}
	}

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;
}

/**
*
*/
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();

}

}

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();

	}

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();
	}

}

i want to add a complete linked list at the end of another linked list in java......pls help

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;
}

}