Problem statement: Merging a sorted lists to a single

// Here is a simplex LinkedList class simplelinkedist { public int value; public simplelinkedist next = null; public simplelinkedist(int v) { value = v; } }

simplelinkedist temp = null; simplelinkedist listone = new simplelinkedist(0); simplelinkedist listtwo = new simplelinkedist(1); // Fill the first one with even numbers temp = listone; for (int i = 2; i < 12; i = i + 2) { temp.next = new simplelinkedist(i); temp = temp.next; } // Fill the second one with ODD numberss temp = listtwo; for (int i = 3; i < 13; i = i + 2) { temp.next = new simplelinkedist(i); temp = temp.next; } // Display the first one temp = listone; label1.Text = ""; while (temp!= null) { label1.Text += temp.value.ToString() + "\n\r"; temp = temp.next; } // Display the second one temp = listtwo; label2.Text = ""; while (temp != null) { label2.Text += temp.value.ToString() + "\n\r"; temp = temp.next; } //Merge them and show simplelinkedist mergedone = mergetheLists(listone, listtwo); // Display them temp = mergedone; label3.Text = ""; while (temp != null) { label3.Text += temp.value.ToString() + "\n\r"; temp = temp.next; }

// Here goes the Merging Function private simplelinkedist mergetheLists(simplelinkedist a, simplelinkedist b ) { if ((a == null) && (b == null)) { return null; } simplelinkedist myanswer = null; if(b==null) { myanswer = a; myanswer.next = mergetheLists(a.next, null); } else if (a == null) { myanswer = b; myanswer.next = mergetheLists(null, b.next); } else { if (a.value < b.value) { myanswer = a; myanswer.next = mergetheLists(a.next, b); } else { myanswer = b; myanswer.next = mergetheLists(a, b.next); } } return myanswer; }

Assumptions: This methods Think that the given arrays are sorted in ASC order. I prefer to add the code for desc order too.... In any case caller has to pass right boolean (asc/desc) and right Linked lists :) So //Merge them and show simplelinkedist mergedone = mergetheLists(listone, listtwo,true); private simplelinkedist mergetheLists(simplelinkedist a, simplelinkedist b ,bool asc) { if ((a == null) && (b == null)) { return null; } simplelinkedist myanswer = null; if(b==null) { myanswer = a; myanswer.next = mergetheLists(a.next, null,asc); } else if (a == null) { myanswer = b; myanswer.next = mergetheLists(null, b.next,asc); } else { if (asc) { if (a.value < b.value) { myanswer = a; myanswer.next = mergetheLists(a.next, b, asc); } else { myanswer = b; myanswer.next = mergetheLists(a, b.next, asc); } } else { if (a.value > b.value) { myanswer = a; myanswer.next = mergetheLists(a.next, b, asc); } else { myanswer = b; myanswer.next = mergetheLists(a, b.next, asc); } } } return myanswer; }

Can we do it non recursively and for two sorted arrays of integers?

for some reason I don't like using recursion mostly memory usage is a big concern merging two sorted "arrays" is the problemstatement. But the code uses linkedlist.

If code is using singly linked list, is it checking for loops in it?

Little more help to the processor would be with thefollowing changes private void sweepneighbours(int iii, int jjj,bool diag ) { if ((iii < width) && (jjj < height)) { //sweep self if (((int)TwoDimArray.GetValue(iii, jjj)) != 0) { // This is an important step -- otherwise we will endup recusive call for neighbours MyOwnArray.SetValue(true, iii, jjj); //sweep top left if ( diag&& ((iii - 1) > -1) && ((jjj - 1) > -1) && ((bool)MyOwnArray.GetValue(iii - 1, jjj - 1) == false ) ) { if (((int)TwoDimArray.GetValue(iii - 1, jjj - 1)) != 0) { sweepneighbours(iii - 1, jjj - 1, diag); } else { MyOwnArray.SetValue(true, iii - 1, jjj - 1); } } //sweep top == Already done if ( ((jjj - 1) > -1) && ((bool)MyOwnArray.GetValue(iii, jjj - 1) == false) ) { if (((int)TwoDimArray.GetValue(iii, jjj - 1)) != 0) { sweepneighbours(iii, jjj - 1, diag); } else MyOwnArray.SetValue(true, iii, jjj - 1); } //sweep topright == Already done if ( diag&& ((iii + 1) < width) && ((jjj - 1) > -1) && ((bool)MyOwnArray.GetValue(iii+1, jjj - 1) == false) ) { if (((int)TwoDimArray.GetValue(iii + 1, jjj - 1)) != 0) { sweepneighbours(iii + 1, jjj - 1, diag); } else MyOwnArray.SetValue(true, iii + 1, jjj - 1); } //sweep left == Already done if ( ((iii - 1) > -1) && ((bool)MyOwnArray.GetValue(iii - 1, jjj) == false) ) { if (((int)TwoDimArray.GetValue(iii - 1, jjj)) != 0) { sweepneighbours(iii - 1, jjj, diag); } else MyOwnArray.SetValue(true, iii - 1, jjj); } //sweep right if ( ((iii + 1) < width) && ((bool)MyOwnArray.GetValue(iii + 1, jjj) == false) ) { if (((int)TwoDimArray.GetValue(iii + 1, jjj)) != 0) { sweepneighbours(iii + 1, jjj, diag); } else MyOwnArray.SetValue(true, iii + 1, jjj); } //sweep bottomleft if ( diag&& ((iii - 1) > -1) && ((jjj + 1) < height) && ((bool)MyOwnArray.GetValue(iii - 1, jjj + 1) == false) ) { if (((int)TwoDimArray.GetValue(iii - 1, jjj + 1)) != 0) { sweepneighbours(iii - 1, jjj + 1, diag); } else MyOwnArray.SetValue(true, iii - 1, jjj + 1); } //sweep bottom if ( ((jjj + 1) < width) && ((bool)MyOwnArray.GetValue(iii, jjj + 1) == false) ) { if (((int)TwoDimArray.GetValue(iii, jjj + 1)) != 0) { sweepneighbours(iii, jjj + 1, diag); } else MyOwnArray.SetValue(true, iii, jjj + 1); } //sweep bottom right if ( diag&& ((iii + 1) < width) && ((jjj + 1) < height) && ((bool)MyOwnArray.GetValue(iii + 1 , jjj + 1) == false) ) { if (((int)TwoDimArray.GetValue(iii + 1, jjj + 1)) != 0) { sweepneighbours(iii + 1, jjj + 1, diag); } else MyOwnArray.SetValue(true, iii + 1, jjj + 1); } } } }