CareerCup

public Node MergeTwoSortedLinkedLists(Node listNode1, Node listNode2) {
if (listNode1 == null)
return listNode2;
if (listNode2 == null)
return listNode1;

if (listNode1.data < listNode2.data) {
listNode1.next = MergeLists(listNode1.next, listNode2);
return listNode1;
}
else {
// if listNode2.data and listNode.data is equal or listNode1.data is greater than listNode2.data
listNode2.next = MergeLists(listNode2.next, listNode1);
return listNode2;
}
}

public LinkedList<int> Merge(LinkedList<int> a, LinkedList<int> b)
        {
            if (a == null) return b;
            if (b == null) return a;

            LinkedListNode<int> Larger_current = null;
            LinkedListNode<int> Smaller_current = null;

            LinkedList<int> LargerLinkedList = null;
            LinkedList<int> SmallerMergedLinkedList = null;

            if (a.Count >= b.Count)
            {
                LargerLinkedList = a;
                SmallerMergedLinkedList = b;

                Larger_current = a.First;
                Smaller_current = b.First;
            }
            else
            {
                LargerLinkedList = b;
                SmallerMergedLinkedList = a;

                Larger_current = b.First;
                Smaller_current = a.First;
            }

            while (Larger_current != null)
            {
                if (Larger_current.Value < Smaller_current.Value)
                {
                    int val = Larger_current.Value;
                    SmallerMergedLinkedList.AddBefore(Smaller_current, val);
                }
                else
                {
                    while (Smaller_current != null)
                    {
                        if (Larger_current.Value < Smaller_current.Value)
                        {
                            SmallerMergedLinkedList.AddBefore(Smaller_current, Larger_current.Value);
                            break;
                        }
                        Smaller_current = Smaller_current.Next;
                    }
                }
                Larger_current = Larger_current.Next;
            }

            LinkedListNode<int> head = SmallerMergedLinkedList.First;

            return SmallerMergedLinkedList;

            //while (head != null)
            //{
            //    Console.WriteLine(head.Value);
            //    head = head.Next;
            //}
            //Console.ReadLine();
        }

// using collections in JAva
LinkedList<Integer> ll1 = new LinkedList<Integer>();
ll1.add(40);
ll1.add(43);
ll1.add(46);
ll1.add(50);
ll1.add(61);

LinkedList<Integer> ll2 = new LinkedList<Integer>();
ll2.add(1);
ll2.add(40);
ll2.add(60);
ll2.add(70);

LinkedList<Integer> res = new LinkedList<Integer>();
res.addAll(ll1);
res.removeAll(ll2);// if ne duplicates r there, first remove n then merge
res.addAll(ll2);
Collections.sort(res);

System.out.println(res);

package practice.careercup;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static java.util.stream.Collectors.toList;

public class Merge2SortedList {

    public static void main(String[] args) {
        List<Integer> firstList = Arrays.asList(8,2,6,12,4,14,21,13).stream().sorted().collect(toList());
        List<Integer> secondList = Arrays.asList(32,17,4,1,20).stream().sorted().collect(toList());

        int firstIndex = 0;
        int secondIndex = 0;

        List<Integer> mergedList = new ArrayList<>();
        while (firstIndex + secondIndex <= firstList.size() + secondList.size()) {
            if (secondIndex == secondList.size()) {
                while (firstIndex < firstList.size()) {
                    mergedList.add(firstList.get(firstIndex));
                    firstIndex++;
                }
                break;
            }

            if (firstIndex == firstList.size()) {
                while (secondIndex < secondList.size()) {
                    mergedList.add(secondList.get(secondIndex));
                    secondIndex++;
                }
                break;
            }

            if (firstList.get(firstIndex) > secondList.get(secondIndex)) {
                mergedList.add(secondList.get(secondIndex));
                if (secondList.size() > secondIndex ) {
                    secondIndex++;
                }
            } else {
                mergedList.add(firstList.get(firstIndex));
                if (firstList.size() > firstIndex ) {
                    firstIndex++;
                }
            }
        }

        System.out.println(mergedList);
    }
}

public static void main(String args[]) {
		LList head1 = new LList(19);
		head1.next = new LList(450);
		head1.next.next = new LList(540);
		head1.next.next.next = new LList(640);
		LList head2 = new LList(10);
		head2.next = new LList(45);
		head2.next.next = new LList(504);
		LList temp = mergeLists(head1, head2);
		while (temp != null) {
			System.out.print(temp + " ");
			temp = temp.next;
		}
	}

	private static LList mergeLists(LList head1, LList head2) {
		if (head1 == null)
			return head2;
		if (head2 == null)
			return head1;
		LList temp = null;
		if (head1.data < head2.data) {
			temp = head1;
			temp.next = mergeLists(head1.next, head2);
			return temp;
		} else {
			temp = head2;
			temp.next = mergeLists(head1, head2.next);
			return temp;
		}
	}

// This is a C++ code without recursion.

class LNode
{
public:

LNode* next_;

int data_;

};

// Calling from main function
{

vector<int> list1 = { 41, 36, 12, 6, 3, 2, 0 };

vector<int> list2 = { 40, 22, 11, 7, 6, 5, 4, 1 };


List lx;
lx.init( list1 );

List ly;
ly.init( list2 );

LNode* nl = mergeSortedLists( lx.head_, ly.head_ );

List nlist; nlist.head_ = nl;

nlist.show();

}

LNode* mergeSortedLists( LNode* l1, LNode* l2 )
{
LNode* merged = nullptr;

if( l1->data_ < l2->data_ )
{
merged = l1;
}
else
{
merged = l2;
}

this->merge( l1, l2 );

return merged;

}


void merge( LNode* l1, LNode* l2 )
{

LNode* c = l1;
LNode* p = c; LNode* ot = l2;

c = c->next_;

while( c )
{

if( c->data_ < ot->data_ )
{

c = c->next_;
p = p->next_;

}
else
{
LNode* tmp = c;

p->next_ = ot; p = ot;

c = ot->next_;

ot = tmp;

}

} // end while

p->next_ = ot;

}