Interview Question: Merge two sorted singly linked lists without creating new nodes

This is a programming question asked during a written test for an interview. "You have two singly linked lists that are already sorted, you have to merge them and return a the head of the new list without creating any new extra nodes. The returned list should be sorted as well"

The method signature is: Node MergeLists(Node list1, Node list2);

Node class is below:

class Node{
    int data;
    Node next;
}

I tried many solutions but not creating an extra node screws things. Please help.

Here is the accompanying blog entry http://techieme.in/merging-two-sorted-singly-linked-list/

Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  if (list1.data < list2.data) {
    list1.next = MergeLists(list1.next, list2);
    return list1;
  } else {
    list2.next = MergeLists(list2.next, list1);
    return list2;
  }
}

Recursion should not be needed to avoid allocating a new node:

Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  Node head;
  if (list1.data < list2.data) {
    head = list1;
  } else {
    head = list2;
    list2 = list1;
    list1 = head;
  }
  while(list1.next != null) {
    if (list1.next.data > list2.data) {
      Node tmp = list1.next;
      list1.next = list2;
      list2 = tmp;
    }
    list1 = list1.next;
  } 
  list1.next = list2;
  return head;
}

Node MergeLists(Node node1, Node node2)
{
   if(node1 == null)
      return node2;
   else (node2 == null)
      return node1;
	  
   Node head;
   if(node1.data < node2.data)
   {
      head = node1;
	  node1 = node1.next;
   else
   {
      head = node2;
	  node2 = node2.next;
   }
   
   Node current = head;
   while((node1 != null) ||( node2 != null))
   {
      if (node1 == null) {
         current.next = node2;
		 return head;
	  }
      else if (node2 == null) {
         current.next = node1;
		 return head;
	  }
	  
      if (node1.data < node2.data)
      {
	      current.next = node1;
          current = current.next;
		  
	      node1 = node1.next;
      }
	  else
      {
	      current.next = node2;
          current = current.next;
		  
	      node2 = node2.next;
      }
   }
   current.next = NULL // needed to complete the tail of the merged list
   return head;

}

Look ma, no recursion!

struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *result, **tail;

for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) {
        if (cmp(one,two) <=0) { *tail = one; one=one->next; }
        else { *tail = two; two=two->next; }
        }
*tail = one ? one: two;
return result;
}

Here is the algorithm on how to merge two sorted linked lists A and B:

while A not empty or B not empty:
   if first element of A < first element of B:
      remove first element from A
      insert element into C
   end if
   else:
      remove first element from B
      insert element into C
end while

Here C will be the output list.

Iteration can be done as below. Complexity = O(n)

public static LLNode mergeSortedListIteration(LLNode nodeA, LLNode nodeB) {
	LLNode mergedNode ;
	LLNode tempNode ;      

	if (nodeA == null) {
	    return nodeB;
	  } 
	  if (nodeB == null) {
	    return nodeA;
	  }     


	if ( nodeA.getData() < nodeB.getData())
	{
	    mergedNode = nodeA;
	    nodeA = nodeA.getNext();
	}
	else
	{
	    mergedNode = nodeB;
	    nodeB = nodeB.getNext();
	}

	tempNode = mergedNode; 

	while (nodeA != null && nodeB != null)
	{           

	    if ( nodeA.getData() < nodeB.getData())
	    {               
	        mergedNode.setNext(nodeA);
	        nodeA = nodeA.getNext();
	    }
	    else
	    {
	        mergedNode.setNext(nodeB);
	        nodeB = nodeB.getNext();                
	    }       
	    mergedNode = mergedNode.getNext();
	}

	if (nodeA != null)
	{
	    mergedNode.setNext(nodeA);
	}

	if (nodeB != null)
	{
	    mergedNode.setNext(nodeB);
	}       
	return tempNode;
}

Node mergeList(Node h1, Node h2) {
	if (h1 == null) return h2;
	if (h2 == null) return h1;
	Node head;
	if (h1.data < h2.data) {
		head = h1;
	} else {
		head = h2;
		h2 = h1;
		h1 = head;
	}
	
	while (h1.next != null && h2 != null) {
		if (h1.next.data < h2.data) {
			h1 = h1.next;
		} else {
			Node afterh2 = h2.next;
			Node afterh1 = h1.next;
			h1.next = h2;
			h2.next = afterh1;
			
			if (h2.next != null) {
				h2 = afterh2;
			}
		}
	}
	return head;
}

A simple iterative solution.

Node* MergeLists(Node* A, Node* B)
{
    //handling the corner cases
    
    //if both lists are empty
    if(!A && !B)
    {
        cout << "List is empty" << endl;
        return 0;
    }
    //either of list is empty
    else if(!A) return B;
    else if(!B) return A;
    else
    {
        Node* head = NULL;//this will be the head of the newList
        Node* previous = NULL;//this will act as the
        
        /* In this algorithm we will keep the
         previous pointer that will point to the last node of the output list.
         And, as given we have A & B as pointer to the given lists.
         
         The algorithm will keep on going untill either one of the list become empty.
         Inside of the while loop, it will divide the algorithm in two parts:
            - First, if the head of the output list is not obtained yet
            - Second, if head is already there then we will just compare the values and keep appending to the 'previous' pointer.
         When one of the list become empty we will append the other 'left over' list to the output list.
         */
         while(A && B)
         {
             if(!head)
             {
                 if(A->data <= B->data)
                 {
                     head = A;//setting head of the output list to A
                     previous = A; //initializing previous
                     A = A->next;
                 }
                 else
                 {
                     head = B;//setting head of the output list to B
                     previous = B;//initializing previous
                     B = B->next;
                 }
             }
             else//when head is already set
             {
                 if(A->data <= B->data)
                 {
                     if(previous->next != A)
                         previous->next = A;
                     A = A->next;//Moved A forward but keeping B at the same position
                 }
                 else
                 {
                     if(previous->next != B)
                         previous->next = B;
                     B = B->next; //Moved B forward but keeping A at the same position
                 }
                 previous = previous->next;//Moving the Output list pointer forward
             }
         }
        //at the end either one of the list would finish
        //and we have to append the other list to the output list
        if(!A)
            previous->next = B;
        
        if(!B)
            previous->next = A;
        
        return head; //returning the head of the output list
    }
}

This could be done without creating the extra node, with just an another Node reference passing to the parameters (Node temp).

private static Node mergeTwoLists(Node nodeList1, Node nodeList2, Node temp) {
	if(nodeList1 == null) return nodeList2;
	if(nodeList2 == null) return nodeList1;
	
	if(nodeList1.data <= nodeList2.data){
		temp = nodeList1;
        temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp);
    }
	else{
		temp = nodeList2;
		temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp);
    }
	return temp;
}

I would like to share how i thought the solution... i saw the solution that involves recursion and they are pretty amazing, is the outcome of well functional and modular thinking. I really appreciate the sharing.

I would like to add that recursion won't work for big lits, the stack calls will overflow; so i decided to try the iterative approach... and this is what i get.

The code is pretty self explanatory, i added some inline comments to try to assure this.

If you don't get it, please notify me and i will improve the readability (perhaps i am having a misleading interpretation of my own code).

import java.util.Random;


public class Solution {

    public static class Node<T extends Comparable<? super T>> implements Comparable<Node<T>> {

        T data;
        Node next;

        @Override
        public int compareTo(Node<T> otherNode) {
            return data.compareTo(otherNode.data);
        }

        @Override
        public String toString() {
            return ((data != null) ? data.toString() + ((next != null) ? "," + next.toString() : "") : "null");
        }
    }

    public static Node merge(Node firstLeft, Node firstRight) {
        combine(firstLeft, firstRight);
        return Comparision.perform(firstLeft, firstRight).min;

    }

    private static void combine(Node leftNode, Node rightNode) {
        while (leftNode != null && rightNode != null) {
            // get comparision data about "current pair of nodes being analized".
            Comparision comparision = Comparision.perform(leftNode, rightNode);
            // stores references to the next nodes
            Node nextLeft = leftNode.next; 
            Node nextRight = rightNode.next;
            // set the "next node" of the "minor node" between the "current pair of nodes being analized"...
            // ...to be equals the minor node between the "major node" and "the next one of the minor node" of the former comparision.
            comparision.min.next = Comparision.perform(comparision.max, comparision.min.next).min;
            if (comparision.min == leftNode) {
                leftNode = nextLeft;
            } else {
                rightNode = nextRight;
            }
        }
    }
    
/** Stores references to two nodes viewed as one minimum and one maximum. The static factory method populates properly the instance being build */
    private static class Comparision {

        private final Node min;
        private final Node max;

        private Comparision(Node min, Node max) {
            this.min = min;
            this.max = max;
        }

        private static Comparision perform(Node a, Node b) {
            Node min, max;
            if (a != null && b != null) {
                int comparision = a.compareTo(b);
                if (comparision <= 0) {
                    min = a;
                    max = b;
                } else {
                    min = b;
                    max = a;
                }
            } else {
                max = null;
                min = (a != null) ? a : b;
            }
            return new Comparision(min, max);
        }
    }

// Test example....
    public static void main(String args[]) {
        Node firstLeft = buildList(20);
        Node firstRight = buildList(40);
        Node firstBoth = merge(firstLeft, firstRight);
        System.out.println(firstBoth);
    }

// someone need to write something like this i guess...
    public static Node buildList(int size) {
        Random r = new Random();
        Node<Integer> first = new Node<>();
        first.data = 0;
        first.next = null;
        Node<Integer> current = first;
        Integer last = first.data;
        for (int i = 1; i < size; i++) {
            Node<Integer> node = new Node<>();
            node.data = last + r.nextInt(5);
            last = node.data;
            node.next = null;
            current.next = node;
            current = node;
        }
        return first;
    }

}

I show below an iterative solution. A recursive solution would be more compact, but since we don't know the length of the lists, recursion runs the risk of stack overflow.

The basic idea is similar to the merge step in merge sort; we keep a pointer corresponding to each input list; at each iteration, we advance the pointer corresponding to the smaller element. However, there's one crucial difference where most people get tripped. In merge sort, since we use a result array, the next position to insert is always the index of the result array. For a linked list, we need to keep a pointer to the last element of the sorted list. The pointer may jump around from one input list to another depending on which one has the smaller element for the current iteration.

With that, the following code should be self-explanatory.

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    ListNode first = l1;
    ListNode second = l2;
    ListNode head = null;
    ListNode last = null;
    
    while (first != null && second != null) {
        if (first.val < second.val) {
            if (last != null) {
                last.next = first;
            }
            last = first;
            first = first.next;
        } else {
            if (last != null) {
                last.next = second;
            }
            last = second;
            second = second.next;
        }
        if (head == null) {
            head = last;
        }
    }
    
    if (first == null) {
        last.next = second;
    }
    if (second == null) {
        last.next = first;
    }
    
    return head;
}

Simple code in javascript to merge two linked list inplace.

function mergeLists(l1, l2) {
    let head = new ListNode(0); //dummy
    let curr = head;
    while(l1 && l2) {
        if(l2.val >= l1.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2=l2.next
        }
        curr = curr.next;
    }
    if(!l1){
        curr.next=l2;
    }
    if(!l2){
        curr.next=l1;
    } 
    return head.next;
}

First of all understand the mean of "without creating any new extra nodes", As I understand it does not mean that I can not have pointer(s) which points to an existing node(s).

You can not achieve it without talking pointers to existing nodes, even if you use recursion to achieve the same, system will create pointers for you as call stacks. It is just like telling system to add pointers which you have avoided in your code.

Simple function to achieve the same with taking extra pointers:

typedef struct _LLNode{
    int             value;
    struct _LLNode* next;
}LLNode;


LLNode* CombineSortedLists(LLNode* a,LLNode* b){
    if(NULL == a){
        return b;
    }
    if(NULL == b){
        return a;
    }
    LLNode* root  = NULL;
    if(a->value < b->value){
        root = a;
        a = a->next;
    }
    else{
        root = b;
        b    = b->next;
    }
    LLNode* curr  = root;
    while(1){
        if(a->value < b->value){
            curr->next = a;
            curr = a;
            a=a->next;
            if(NULL == a){
                curr->next = b;
                break;
            }
        }
        else{
            curr->next = b;
            curr = b;
            b=b->next;
            if(NULL == b){
                curr->next = a;
                break;
            }
        }
    }
    return root;
}

public static Node merge(Node h1, Node h2) {
	
	Node h3 = new Node(0);
	Node current = h3;
	
	boolean isH1Left = false;
	boolean isH2Left = false;
	
	while (h1 != null || h2 != null) {
		if (h1.data <= h2.data) {
			current.next = h1;
			h1 = h1.next;
		} else {
			current.next = h2;
			h2 = h2.next;
		}
		current = current.next;
		
		if (h2 == null && h1 != null) {
			isH1Left = true;
			break;
		}
		
		if (h1 == null && h2 != null) {
			isH2Left = true;
			break;
		}
	}
	
	if (isH1Left) {
		while (h1 != null) {
			current.next = h1;
			current = current.next;
			h1 = h1.next;
		}
	} 
	
	if (isH2Left) {
		while (h2 != null) {
			current.next = h2;
			current = current.next;
			h2 = h2.next;
		}
	}
	
	h3 = h3.next;
	
	return h3;
}

Node * merge_sort(Node *a, Node *b){
   Node *result = NULL;
   if(a ==  NULL)
      return b;
   else if(b == NULL)
      return a;

  /* For the first node, we would set the result to either a or b */
    if(a->data <= b->data){
       result = a;
    /* Result's next will point to smaller one in lists 
       starting at a->next  and b */
      result->next = merge_sort(a->next,b);
    }
    else {
      result = b;
     /*Result's next will point to smaller one in lists 
       starting at a and b->next */
       result->next = merge_sort(a,b->next);
    }
    return result;
 }

Please refer to my blog post for http://www.algorithmsandme.com/2013/10/linked-list-merge-two-sorted-linked.html

Node MergeLists(Node list1, Node list2) {
	//if list is null return other list 
   if(list1 == null)
   {
      return list2;
   }
   else if(list2 == null)
   {
      return list1;
   }
   else
   {
        Node head;
		//Take head pointer to the node which has smaller first data node
        if(list1.data < list2.data)
        {
            head = list1;
            list1 = list1.next;
        }
        else
        {
           head = list2;
           list2 = list2.next;
        }
        Node current = head;
		//loop till both list are not pointing to null
        while(list1 != null || list2 != null)
        {
			//if list1 is null, point rest of list2 by current pointer 
            if(list1 == null){
               current.next = list2;
               return head;
            }
			//if list2 is null, point rest of list1 by current pointer 
            else if(list2 == null){
               current.next = list1;
               return head;
            }
			//compare if list1 node data is smaller than list2 node data, list1 node will be
			//pointed by current pointer
            else if(list1.data < list2.data)
            {
                current.next = list1;
                current = current.next;
                list1 = list1.next;
            }
            else
            {
                current.next = list2;
                current = current.next;
                list2 = list2.next;
            }
        }      
    return head;
    }      
}

Here is a complete working example that uses the linked list implemented java.util. You can just copy paste the code below inside a main() method.

        LinkedList<Integer> dList1 = new LinkedList<Integer>();
        LinkedList<Integer> dList2 = new LinkedList<Integer>();
        LinkedList<Integer> dListMerged = new LinkedList<Integer>();

        dList1.addLast(1);
        dList1.addLast(8);
        dList1.addLast(12);
        dList1.addLast(15);
        dList1.addLast(85);

        dList2.addLast(2);
        dList2.addLast(3);
        dList2.addLast(12);
        dList2.addLast(24);
        dList2.addLast(85);
        dList2.addLast(185);

        int i = 0;
        int y = 0;
        int dList1Size = dList1.size();
        int dList2Size = dList2.size();
        int list1Item = dList1.get(i);
        int list2Item = dList2.get(y);
        while (i < dList1Size || y < dList2Size) {

            if (i < dList1Size) {

                if (list1Item <= list2Item || y >= dList2Size) {
                    dListMerged.addLast(list1Item);
                    i++;
                    if (i < dList1Size) {
                        list1Item = dList1.get(i);
                    }
                }
            }


            if (y < dList2Size) {

                if (list2Item <= list1Item || i >= dList1Size) {
                    dListMerged.addLast(list2Item);
                    y++;
                    if (y < dList2Size) {
                        list2Item = dList2.get(y);
                    }
                }
            }

        }

        for(int x:dListMerged)
        {
            System.out.println(x);
        }

Recursive way(variant of Stefan answer)

 MergeList(Node nodeA, Node nodeB ){
    	if(nodeA==null){return nodeB};
    	if(nodeB==null){return nodeA};
    
    if(nodeB.data<nodeA.data){
    	Node returnNode = MergeNode(nodeA,nodeB.next);
    	nodeB.next = returnNode;
    	retturn nodeB;
    }else{
    	Node returnNode = MergeNode(nodeA.next,nodeB);
    	nodeA.next=returnNode;
    	return nodeA;
    }

Consider below linked list to visualize this

2>4 list A 1>3 list B

Almost same answer(non recursive) as Stefan but with little more comments/meaningful variable name. Also covered double linked list in comments if someone is interested

Consider the example

5->10->15>21 // List1

2->3->6->20 //List2

Node MergeLists(List list1, List list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

if(list1.head.data>list2.head.data){
  listB =list2; // loop over this list as its head is smaller
  listA =list1;
} else {
  listA =list2; // loop over this list
  listB =list1;
}


listB.currentNode=listB.head;
listA.currentNode=listA.head;

while(listB.currentNode!=null){

  if(listB.currentNode.data<listA.currentNode.data){
    Node insertFromNode = listB.currentNode.prev; 
    Node startingNode = listA.currentNode;
    Node temp = inserFromNode.next;
    inserFromNode.next = startingNode;
    startingNode.next=temp;
    
    startingNode.next.prev= startingNode; // for doubly linked list
    startingNode.prev=inserFromNode;  // for doubly linked list


    listB.currentNode= listB.currentNode.next;
    listA.currentNode= listA.currentNode.next;

  } 
  else
  {
    listB.currentNode= listB.currentNode.next;

  }

}

My take on the question is as below:

Pseudocode:

Compare the two heads A and B. 
If A <= B, then add A and move the head of A to the next node. 
Similarly, if B < A, then add B and move the head of B to the next node B.
If both A and B are NULL then stop and return.
If either of them is NULL, then traverse the non null head till it becomes NULL.

Code:

public Node mergeLists(Node headA, Node headB) {
	Node merge = null;
	// If we have reached the end, then stop.
	while (headA != null || headB != null) {
		// if B is null then keep appending A, else check if value of A is lesser or equal than B
		if (headB == null || (headA != null && headA.data <= headB.data)) {
			// Add the new node, handle addition separately in a new method.
			merge = add(merge, headA.data);
			// Since A is <= B, Move head of A to next node
			headA = headA.next;
		// if A is null then keep appending B, else check if value of B is lesser than A
		} else if (headA == null || (headB != null && headB.data < headA.data)) {
			// Add the new node, handle addition separately in a new method.
			merge = add(merge, headB.data);
			// Since B is < A, Move head of B to next node
			headB = headB.next;
		}
	}
	return merge;
}

public Node add(Node head, int data) {
	Node end = new Node(data);
	if (head == null) {
		return end;
	}

	Node curr = head;
	while (curr.next != null) {
		curr = curr.next;
	}

	curr.next = end;
	return head;
}

        /* Simple/Elegant Iterative approach in Java*/    
        private static LinkedList mergeLists(LinkedList list1, LinkedList list2) {
            		Node head1 = list1.start;
            		Node head2 = list2.start;
                    if (list1.size == 0)
    			    return list2;
    		        if (list2.size == 0)
    			    return list1;        		
                    LinkedList mergeList = new LinkedList();
            		while (head1 != null && head2 != null) {
            			if (head1.getData() < head2.getData()) {
            				int data = head1.getData();
            				mergeList.insert(data);
            				head1 = head1.getNext();
            			} else {
            				int data = head2.getData();
            				mergeList.insert(data);
            				head2 = head2.getNext();
            			}
            		}
            		while (head1 != null) {
            			int data = head1.getData();
            			mergeList.insert(data);
            			head1 = head1.getNext();
            		}
            		while (head2 != null) {
            			int data = head2.getData();
            			mergeList.insert(data);
            			head2 = head2.getNext();
            		}
            		return mergeList;
            	}

/* Build-In singly LinkedList class in Java*/
class LinkedList {
	Node start;
	int size = 0;

	void insert(int data) {
		if (start == null)
			start = new Node(data);
		else {
			Node temp = start;
			while (temp.getNext() != null) {
				temp = temp.getNext();
			}
			temp.setNext(new Node(data));
		}
		size++;
	}

	@Override
	public String toString() {

		String str = "";
		Node temp=start;
		while (temp != null) {
			str += temp.getData() + "-->";
			temp = temp.getNext();
		}
		return str;
	}

}

LLNode *mergeSorted(LLNode *h1, LLNode *h2) 
{ 
  LLNode *h3=NULL;
  LLNode *h3l;
  if(h1==NULL && h2==NULL)
    return NULL; 
  if(h1==NULL) 
    return h2; 
  if(h2==NULL) 
    return h1; 
  if(h1->data<h2->data) 
  {
    h3=h1;
    h1=h1->next; 
  }
  else 
  { 
    h3=h2; 
    h2=h2->next; 
  }
  LLNode *oh=h3;
  while(h1!=NULL && h2!=NULL) 
  {
    if(h1->data<h2->data) 
    {
      h3->next=h1;
      h3=h3->next;
      h1=h1->next; 
    } 
    else 
    {
      h3->next=h2; 
      h3=h3->next; 
      h2=h2->next; 
    } 
  } 
  if(h1==NULL)
    h3->next=h2;
  if(h2==NULL)
    h3->next=h1;
  return oh;
}

// Common code for insert at the end
        private void insertEnd(int data) {
        		Node newNode = new Node(data);
        		if (head == null) {
        			newNode.next = head;
        			head = tail = newNode;
        			return;
        		}
        		Node tempNode = tail;
        		tempNode.next = newNode;
        		tail = newNode;
        	}
    
    private void mergerTwoSortedListInAscOrder(Node tempNode1, Node tempNode2) {
    
    		if (tempNode1 == null && tempNode2 == null)
    			return;
    		if (tempNode1 == null) {
    			head3 = tempNode2;
    			return;
    		}
    		if (tempNode2 == null) {
    			head3 = tempNode1;
    			return;
    		}
    
    		while (tempNode1 != null && tempNode2 != null) {
    
    			if (tempNode1.mData < tempNode2.mData) {
    				insertEndForHead3(tempNode1.mData);
    				tempNode1 = tempNode1.next;
    			} else if (tempNode1.mData > tempNode2.mData) {
    				insertEndForHead3(tempNode2.mData);
    				tempNode2 = tempNode2.next;
    			} else {
    				insertEndForHead3(tempNode1.mData);
    				insertEndForHead3(tempNode2.mData);
    				tempNode1 = tempNode1.next;
    				tempNode2 = tempNode2.next;
    			}
    
    		}
    		if (tempNode1 != null) {
    			while (tempNode1 != null) {
    				insertEndForHead3(tempNode1.mData);
    				tempNode1 = tempNode1.next;
    			}
    		}
    		if (tempNode2 != null) {
    			while (tempNode2 != null) {
    				insertEndForHead3(tempNode2.mData);
    				tempNode2 = tempNode2.next;
    			}
    		}
    	}

:)GlbMP

I created only one dummy node at the beginning to save myself many 'if' conditions.

	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

		ListNode list1Cursor = l1;
		ListNode list2Cursor = l2;

		ListNode currentNode = new ListNode(-1); // Dummy node
		ListNode head = currentNode;

		while (list1Cursor != null && list2Cursor != null)
		{
			if (list1Cursor.val < list2Cursor.val) {
				currentNode.next = list1Cursor;
				list1Cursor = list1Cursor.next;
				currentNode = currentNode.next;
			} else {
				currentNode.next = list2Cursor;
				list2Cursor = list2Cursor.next;
				currentNode = currentNode.next;
			}
		}

		// Complete the rest
		while (list1Cursor != null) {
			currentNode.next = list1Cursor;
			currentNode = currentNode.next;
			list1Cursor = list1Cursor.next;
		}
		while (list2Cursor != null) {
			currentNode.next = list2Cursor;
			currentNode = currentNode.next;
			list2Cursor = list2Cursor.next;
		}

		return head.next;
	}

public ListNode MergeTwoLists(ListNode l1, ListNode l2) {//c#
ListNode _destNode=null;//Merged List
ListNode _srcNode=null;
ListNode _resHead=null;
if(l1==null || l2==null){//for scenario l1 null or l2 null or both null
    return l1??l2??null;
}
if(l1.val<=l2.val){    
    _destNode=l1;//finding the dest list
   _srcNode=l2;
    _resHead=l1;
}
else{
    _destNode=l2;
     _srcNode=l1;
     _resHead=l2;
}

while(_destNode!=null && _srcNode!=null){
    if(_destNode.val<=_srcNode.val && (_destNode.next==null ||_destNode.next.val>=_srcNode.val)) {
        //appending the values to dest list , if the element from dest list  is less than  element from _srcNode 
            var _temp_l2_currentnode=_srcNode;
            _srcNode=_srcNode.next;
            var _temp_l1_nextnode=_destNode.next;
            _destNode.next=_temp_l2_currentnode;
            _temp_l2_currentnode.next=_temp_l1_nextnode;
            _destNode=_destNode.next;
    }
    else{
          _destNode=_destNode.next;

    }
}
return _resHead;

}

private static Node mergeLists(Node L1, Node L2) {

    Node P1 = L1.val < L2.val ? L1 : L2;
    Node P2 = L1.val < L2.val ? L2 : L1;
    Node BigListHead = P1;
    Node tempNode = null;
    
    while (P1 != null && P2 != null) {
        if (P1.next != null && P1.next.val >P2.val) {
        tempNode = P1.next;
        P1.next = P2;
        P1 = P2;
        P2 = tempNode;
        } else if(P1.next != null) 
        P1 = P1.next;
        else {
        P1.next = P2;
        break;
        }
    }
    
    return BigListHead;
}

void printLL(){
	NodeLL cur = head;
	if(cur.getNext() == null){
		System.out.println("LL is emplty");
	}else{
		//System.out.println("printing Node");
		while(cur.getNext() != null){
			cur = cur.getNext();
			System.out.print(cur.getData()+ " ");

		}
	}
	System.out.println();
}

void mergeSortedList(NodeLL node1, NodeLL node2){
	NodeLL cur1 = node1.getNext();
	NodeLL cur2 = node2.getNext();

	NodeLL cur = head;
	if(cur1 == null){
		cur = node2;
	}

	if(cur2 == null){
		cur = node1;
	}		
	while(cur1 != null && cur2 != null){

		if(cur1.getData() <= cur2.getData()){
			cur.setNext(cur1);
			cur1 = cur1.getNext();
		}
		else{
			cur.setNext(cur2);
			cur2 = cur2.getNext();
		}
		cur = cur.getNext();
	}		
	while(cur1 != null){
		cur.setNext(cur1);
		cur1 = cur1.getNext();
		cur = cur.getNext();
	}		
	while(cur2 != null){
		cur.setNext(cur2);
		cur2 = cur2.getNext();
		cur = cur.getNext();
	}		
	printLL();		
}

Here is the code on how to merge two sorted linked lists headA and headB:

Node* MergeLists1(Node *headA, Node* headB)
{
    Node *p = headA;
    Node *q = headB;
    Node *result = NULL; 
	Node *pp = NULL;
	Node *qq = NULL;
	Node *head = NULL;
    int value1 = 0;
    int value2 = 0;
	if((headA == NULL) && (headB == NULL))
	{
		return NULL;
	}
	if(headA==NULL)
	{
        return headB;
    }
	else if(headB==NULL)
	{
        return headA;
    }
	else
	{
		while((p != NULL) || (q != NULL))
		{
			if((p != NULL) && (q != NULL))
			{
				int value1 = p->data;
				int value2 = q->data;
				if(value1 <= value2)
				{
					pp = p->next;
					p->next = NULL;
					if(result == NULL)
					{
						head = result = p;
					}
					else
					{
						result->next = p;
						result = p;
					}
					p = pp;
				}
				else
				{
					qq = q->next;
					q->next = NULL;
					if(result == NULL)
					{
						head = result = q;
					}
					else
					{
						result->next = q;
						result = q;
					}
					q = qq;
				}
			}
			else
			{
				if(p != NULL)
				{
					pp = p->next;
					p->next = NULL;
					result->next = p;
					result = p;
					p = pp;
				}
				if(q != NULL)
				{
					qq = q->next;
					q->next = NULL;
					result->next = q;
					result = q;
					q = qq;
				}
			}
		}
	}
    return head;
}